home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / estra.me < prev    next >
Text File  |  1992-09-25  |  155KB  |  4,635 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .if t \{ \
  4. .pl 29.7c    \" page length
  5. .po 2.5c    \" page offset (left margin)
  6. .ll 16.5c    \" line length
  7. .lt 16.5c    \" title length
  8. .nr LL 16.5c
  9. .nr )l 29.7c
  10. .nr hm 2c
  11. .nr $r 9    \" factor for vertical spacing
  12. .nr $R \n($r
  13. .sz 12        \" font size
  14. .nr pp 12
  15. .nr sp 12
  16. .nr tp 12
  17. .nr fp 10
  18. .hc ~        \" hyphenation character
  19. .        \" Umlauts and sharp s
  20. .ds A \(A:
  21. .ds O \(O:
  22. .ds U \(U:
  23. .ds a \(a:
  24. .ds o \(o:
  25. .ds u \(u:
  26. .ds s \(ss
  27. .        \"  UMLAUT  \*:u, etc.
  28. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  29. .\}
  30. .if n \{ \
  31. .po 0        \" page offset (left margin)
  32. .ll 78        \" line length
  33. .lt 78        \" title length
  34. .nr $r 4    \" factor for vertical spacing
  35. .nr $R \n($r
  36. .hc ~        \" hyphenation character
  37. .        \" Umlaute und scharfes s
  38. .ds A Ae
  39. .ds O Oe
  40. .ds U Ue
  41. .ds a ae
  42. .ds o oe
  43. .ds u ue
  44. .ds s sz
  45. .\}
  46. .de _
  47. \&\\$1\l'|0\(ul'\\$2
  48. ..
  49. .de FT        \" font for programs
  50. .ft C
  51. .sz -2
  52. ..
  53. .de FR
  54. .ft R
  55. .sz +2
  56. ..
  57. .de []        \" start to display collected references
  58. .uh References
  59. .lp
  60. ..
  61. .de $0        \" collect table of contents
  62. .(x
  63. .ta 2c
  64. .ie '\\$2''    \\$1
  65. .el \\$2.    \\$1
  66. .)x
  67. ..
  68. .de np
  69. .nr $p +1
  70. .ip \\n($p.
  71. ..
  72. .de SH
  73. .sp 0.5
  74. .in -3
  75. .r \\$1
  76. .sp 0.5
  77. .in +3
  78. ..
  79. .de PP
  80. .sp 0.5
  81. ..
  82. .de IP
  83. .ip \\$1 \\$2
  84. ..
  85. .de I
  86. .i \\$1
  87. ..
  88. .de TH
  89. ..
  90. .\"    @(#)bmac.std    2.2    9/9/83;
  91. .\" standard format troff commands
  92. .\" citation formatting strings
  93. .ds [[ [
  94. .ds ]] ]
  95. .ds ], ,\|
  96. .ds ]- -
  97. .ds [. " \&
  98. .ds .] .
  99. .ds [, " \&
  100. .ds ,] ,
  101. .ds [? " \&
  102. .ds ?] ?
  103. .ds [: " \&
  104. .ds :] :
  105. .ds [; " \&
  106. .ds ;] ;
  107. .ds [! " \&
  108. .ds !] !
  109. .ds [" " \&
  110. .ds "] \&"
  111. .ds [' " \&
  112. .ds '] '
  113. .ds [< " \&
  114. .ds >]
  115. .\" reference formmating strings
  116. .ds a] " \&
  117. .ds b] , \&
  118. .ds c] , \&
  119. .ds n] "\& and \&
  120. .ds m] "\& and \&
  121. .ds p] .
  122. .\" reference formmating macros
  123. .de s[   \" start reference
  124. .nh
  125. .IP [\\*([F] 5m
  126. ..
  127. .de e[   \" end reference
  128. .[-
  129. ..
  130. .de []   \" start to display collected references
  131. .LP
  132. ..
  133. .de ][   \" choose format
  134. .ie !"\\*([J"" \{\
  135. .    ie !"\\*([V"" .nr t[ 1    \" journal
  136. .    el            .nr t[ 5    \" conference paper
  137. .\}
  138. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  139. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  140. .el .ie !"\\*([I"" .nr t[ 2    \" book
  141. .el                .nr t[ 0    \" other
  142. .\\n(t[[
  143. ..
  144. .de 0[   \" other
  145. .s[
  146. .if !"\\*([A"" \\*([A\\c
  147. .if !"\\*([T"" , \\*([T\\c
  148. .if !"\\*([V"" , Vol. \\*([V\\c
  149. .if !"\\*([O"" , \\*([O\\c
  150. .if !"\\*([D"" , \\*([D\\c
  151. \&.
  152. .e[
  153. ..
  154. .de 1[ \" journal article
  155. .s[
  156. .if !"\\*([A"" \\*([A,
  157. .if !"\\*([T""  \\*([T,
  158. \\fI\\*([J \\*([V\\fP\c
  159. .if !"\\*([N"" ,\\*([N
  160. .if !"\\*([D"" (\\*([D)\c
  161. .if !"\\*([P"" , \\*([P\c
  162. .if !"\\*([I"" , \\*([I\c
  163. \\&.
  164. .if !"\\*([O"" \\*([O.
  165. .e[
  166. ..
  167. .de 2[ \" book
  168. .s[
  169. .ie !"\\*([A"" \\*([A,
  170. .el .if !"\\*([E"" \{\
  171. .       ie \\n([E-1 \\*([E, eds.,
  172. .       el \\*([E, ed.,\}
  173. .if !"\\*([T"" \\fI\\*([T\\fP,
  174. .rm a[
  175. .if !"\\*([I"" .ds a[ \\*([I
  176. .if !"\\*([C"" \{\
  177. .       if !"\\*(a["" .as a[ , \\&
  178. .       as a[ \\*([C\}
  179. .if !"\\*([D"" \{\
  180. .       if !"\\*(a["" .as a[ , \\&
  181. .       as a[ \\*([D\}
  182. \\*(a[.
  183. .if !"\\*([G"" Gov. ordering no. \\*([G.
  184. .if !"\\*([O"" \\*([O.
  185. .e[
  186. ..
  187. .de 3[ \" article in book
  188. .s[
  189. .if !"\\*([A"" \\*([A,
  190. .if !"\\*([T"" \\*([T,
  191. in \\fI\\*([B\\fP\c
  192. .if !"\\*([V"" , vol. \\*([V
  193. .if !~\\*([E~~ \{\
  194. .       ie , \\n([E-1  \\*([E (editors)\c
  195. .       el , \\*([E (editor)\c\}
  196. .if !"\\*([I"" , \\*([I\c
  197. .if !"\\*([C"" , \\*([C\c
  198. .if !"\\*([D"" , \\*([D\c
  199. .if !"\\*([P"" , \\*([P\c
  200. \\&.
  201. .if !"\\*([O"" \\*([O.
  202. .e[
  203. ..
  204. .de 4[ \" report
  205. .s[
  206. .if !"\\*([A"" \\*([A,
  207. .if !~\\*([E~~ \{\
  208. .       ie \\n([E-1 \\*([E, editors.
  209. .       el \\*([E, editor.\}
  210. \\*([T,
  211. \\*([R\c
  212. .if !"\\*([G"" \& (\\*([G)\c
  213. .if !"\\*([I"" , \\*([I\c
  214. .if !"\\*([C"" , \\*([C\c
  215. .if !"\\*([D"" , \\*([D\c
  216. \\&.
  217. .if !"\\*([O"" \\*([O.
  218. .e[
  219. ..
  220. .de 5[ \" conference paper
  221. .s[
  222. .if !"\\*([A"" \\*([A,
  223. .if !"\\*([T"" \\*([T,
  224. \\fI\\*([J\\fP,
  225. .if !"\\*([C"" \\*([C,
  226. .if !"\\*([D"" \\*([D\c
  227. .if !"\\*([P"" , \\*([P\c
  228. \\&.
  229. .if !"\\*([O"" \\*([O.
  230. .e[
  231. ..
  232. .de [-   \" clean up after yourself
  233. .rm [A [B [C [D
  234. .rm [E [F [G
  235. .rm [I [J [K
  236. .rm [N [O [P
  237. .rm [R [T
  238. .rm [V [W
  239. ..
  240. .\"    @(#)bmac.std    2.2    8/24/83;
  241. .\" standard format troff commands
  242. .\" citation formatting strings
  243. .ds [[ [
  244. .ds ]] ]
  245. .ds ], ,\|
  246. .ds ]- -
  247. .ds [. " \&
  248. .ds .] .
  249. .ds [, " \&
  250. .ds ,] ,
  251. .ds [< " \&
  252. .ds >]
  253. .\" reference formmating strings
  254. .ds c] , \&
  255. .ds n] "" and \&
  256. .ds m] "" and \&
  257. .ds a] " \&
  258. .\" reference formmating macros
  259. .de s[   \" start reference
  260. .nh
  261. .IP [\\*([F] 5m
  262. ..
  263. .de e[   \" end reference
  264. .[-
  265. ..
  266. .de []   \" start to display collected references
  267. .SH
  268. References
  269. .LP
  270. ..
  271. .de ][   \" choose format
  272. .ie !"\\*([J"" \{\
  273. .    ie !"\\*([V"" .nr t[ 1    \" journal
  274. .    el            .nr t[ 5    \" conference paper
  275. .\}
  276. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  277. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  278. .el .ie !"\\*([I"" .nr t[ 2    \" book
  279. .el                .nr t[ 0    \" other
  280. .\\n(t[[
  281. ..
  282. .de 0[   \" other
  283. .s[
  284. .if !"\\*([A"" \\*([A,
  285. .if !"\\*([T"" \\*([T,
  286. .if !"\\*([O"" \\*([O\c
  287. .if !"\\*([D"" , \\*([D\c
  288. \&.
  289. .e[
  290. ..
  291. .de 1[ \" journal article
  292. .s[
  293. .if !"\\*([A"" \\*([A,
  294. .if !"\\*([T"" \\*([T,
  295. \\fI\\*([J \\*([V\\fP,
  296. .if !"\\*([N"" \\*([N
  297. .if !"\\*([D"" (\\*([D),
  298. .if !"\\*([P"" \\*([P\c
  299. .if !"\\*([I"" , \\*([I\c
  300. \\&.
  301. .if !"\\*([O"" \\*([O.
  302. .e[
  303. ..
  304. .de 2[ \" book
  305. .s[
  306. .ie !"\\*([A"" \\*([A,
  307. .el .if !"\\*([E"" \{\
  308. .       ie \\n([E-1 \\*([E, eds.,
  309. .       el \\*([E, ed.,\}
  310. .if !"\\*([T"" \\fI\\*([T\\fP,
  311. .rm a[
  312. .if !"\\*([I"" .ds a[ \\*([I
  313. .if !"\\*([C"" \{\
  314. .       if !"\\*(a["" .as a[ , \\&
  315. .       as a[ \\*([C\}
  316. .if !"\\*([D"" \{\
  317. .       if !"\\*(a["" .as a[ , \\&
  318. .       as a[ \\*([D\}
  319. \\*(a[.
  320. .if !"\\*([G"" Gov. ordering no. \\*([G.
  321. .if !"\\*([O"" \\*([O.
  322. .e[
  323. ..
  324. .de 3[ \" article in book
  325. .s[
  326. .if !"\\*([A"" \\*([A,
  327. .if !"\\*([T"" \\*([T,
  328. in \\fI\\*([B\\fP,
  329. .if !"\\*([V"" vol. \\*([V,
  330. .if !"\\*([E"" \\*([E (ed.),
  331. .if !"\\*([I"" \\*([I,
  332. .if !"\\*([C"" \\*([C,
  333. .if !"\\*([D"" \\*([D\c
  334. .if !"\\*([P"" , \\*([P\c
  335. \\&.
  336. .if !"\\*([O"" \\*([O.
  337. .e[
  338. ..
  339. .de 4[ \" report
  340. .s[
  341. .if !"\\*([A"" \\*([A,
  342. \\*([T,
  343. \\*([R\c
  344. .if !"\\*([G"" \& (\\*([G)\c
  345. .if !"\\*([I"" , \\*([I\c
  346. .if !"\\*([C"" , \\*([C\c
  347. .if !"\\*([D"" , \\*([D\c
  348. \\&.
  349. .if !"\\*([O"" , \\*([O.
  350. .e[
  351. ..
  352. .de 5[ \" conference paper
  353. .s[
  354. .if !"\\*([A"" \\*([A,
  355. .if !"\\*([T"" \\*([T,
  356. \\fI\\*([J\\fP,
  357. .if !"\\*([C"" \\*([C\c
  358. .if !"\\*([D"" , \\*([D\c
  359. .if !"\\*([P"" , \\*([P\c
  360. \\&.
  361. .if !"\\*([O"" , \\*([O.
  362. .e[
  363. ..
  364. .de [-   \" clean up after yourself
  365. .rm [A [B [C [D
  366. .rm [E [F [G
  367. .rm [I [J [K
  368. .rm [N [O [P
  369. .rm [R [T
  370. .rm [V [W
  371. ..
  372. .de s[   \" start reference
  373. .nh
  374. .IP [\\*([F] 10n
  375. ..
  376. .de $0
  377. .(x
  378. .ie '\\$2''\\$1
  379. .el \{\
  380. .ta 0.8c 1.8c 3c
  381. .if '\\$3'1'\{\
  382.  
  383. \fB\\$2.    \\$1\fP\}
  384. .if '\\$3'2'\{\
  385.     \\$2.    \\$1\}
  386. .if '\\$3'3' \{\
  387.         \\$2.    \\$1\}\}
  388. .)x
  389. ..
  390. .de BP
  391. .eh ''%''
  392. .oh ''%''
  393. .bp "\\$1"
  394. ..
  395. .de SH
  396. .if '\\$1'1'\{\
  397. .eh ''%''
  398. .oh ''%''
  399. .sh "\\$1" "\\$2" "\\$3" "\\$4" "\\$5"
  400. .eh '%''\s-2\fR\\n($1. \\$2\fP\s+2'
  401. .oh '\s-2\fR\\n($1. \\$2\fP\s+2''%'\}
  402. .if '\\$1'2'\{\
  403. .oh ''%''
  404. .sh "\\$1" "\\$2" "\\$3" "\\$4" "\\$5"
  405. .oh '\s-2\fR\\n($1.\\n($2. \\$2\fP\s+2''%'\}
  406. .if '\\$1'3'\{\
  407. .sh "\\$1" "\\$2" "\\$3" "\\$4" "\\$5"\}
  408. ..
  409. .de UH
  410. .if '\\$1'1'\{\
  411. .eh ''%''
  412. .oh ''%''
  413. .lp
  414. .b "\\$2"
  415. .lp
  416. .eh '%''\s-2\fR\\$2\fP\s+2'
  417. .oh '\s-2\fR\\$2\fP\s+2''%'\}
  418. .if '\\$1'2'\{\
  419. .oh ''%''
  420. .lp
  421. .b "\\$2"
  422. .lp
  423. .oh '\s-2\fR\\$2\fP\s+2''%'\}
  424. .(x
  425. .ta 0.8c 1.8c 3c
  426. .if '\\$1'1'\{\
  427.  
  428. \fB\\$2\fP\}
  429. .if '\\$1'2'\{\
  430.     \\$2\}
  431. .)x
  432. ..
  433. .de IP
  434. .ip \\$1 \\$2
  435. ..
  436. .de LP
  437. .lp
  438. ..
  439. .        \" halbe Leerzeile
  440. .de HS
  441. .sp 0.5
  442. ..
  443. .        \" Diagramm Anfang
  444. .de DS
  445. .(b
  446. \s-2
  447. .hl
  448. .sp -0.5
  449. ..
  450. .        \" Diagramm Ende
  451. .de DE
  452. .hl
  453. .sp -1
  454. Abb. \\n($1.\\$1: \\$2
  455. .sp 1
  456. .)b
  457. ..
  458. .        \" Diagramm Unterbrechung
  459. .de DB
  460. .)b
  461. .(b
  462. \s-2
  463. ..
  464. .de $f
  465. ..
  466. .\"    $Revision: 2.0 $
  467. .\"    $Author: vielsack $
  468. .\"    $Date: 89/06/22 13:22:27 $
  469. .\"
  470. .(b C
  471. .sz +8
  472. .sp 2
  473. Spezifikation und Implementierung
  474. der Transformation attributierter B\*aume
  475. .sz -4
  476. .sp 5
  477. Bertram Vielsack
  478. .sp 4
  479. Diplomarbeit
  480. .sp 2
  481. Universit\*at Karlsruhe Fakult\*at f\*ur Informatik
  482. .sp 2
  483. Juni 1989
  484. .sp 5
  485. Betreuer:
  486. .sp 1
  487. Prof. Dr. G. Goos
  488. Prof. Dr. S. J\*ahnichen
  489. Dr. J. Grosch
  490. .sz -4
  491. .)b
  492. .bp
  493. .(b F
  494. .sp 35
  495. Hiermit erkl\*are ich, da\*s ich die vorliegende Arbeit
  496. selbst\*andig erstellt habe und keine anderen als die angegebenen
  497. Quellen und Hilfsmittel verwendet habe.
  498. .sp 3
  499. Karlsruhe, im Juni 1989
  500. .sp 3
  501.                                                      (Bertram Vielsack)
  502. .)b
  503. .he ''%''
  504. .BP 4
  505. .SH 1 "Einleitung"
  506. .lp
  507. Bei der Erstellung von \*Ubersetzern spielen Zwischensprachen, die durch
  508. attributierte B\*aume dargestellt werden, eine wichtige Rolle.
  509. Die Zwischensprachen gliedern den komplexen \*Ubersetzungsvorgang
  510. in mehrere Transformationen und damit den Entwurf und die Entwicklung
  511. eines \*Ubersetzers in mehrere unabh\*angige Teilaufgaben.
  512. .lp
  513. Wesentliche Aufgaben beim Bau eines \*Ubersetzers bestehen also
  514. darin, attributierte B\*aume zu transformieren. Das Ergebnis einer
  515. Transformation kann wiederum ein attributierter Baum sein. Andere
  516. Strukturen (Graph, Liste, sequentielle Ausgabe etc.) sind ebenso
  517. m\*oglich. Der einheitlichen Darstellung der Eingabe steht also eine
  518. Vielfalt an M\*oglichkeiten zur Darstellung der Ausgabe gegen\*uber.
  519. .lp
  520. Ein Ziel der vorliegenden Arbeit ist die Entwicklung einer
  521. Spezifikationssprache (ESTRAL\**)
  522. .(f
  523. \**ESTRAL -
  524. .b "E" "fficient"
  525. .b "S" "tructure"
  526. tree
  527. .b "TRA" "nsformation"
  528. .b "L" "anguage"
  529. .)f
  530. zur Beschreibung von Transformationen. Diese Sprache mu\*s einerseits
  531. an die einheitliche Struktur der Eingabe angepa\*st sein.
  532. Andererseits m\*ussen universelle Mittel zur Beschreibung der Ausgabe
  533. bereit gestellt werden.
  534. .lp
  535. Zur automatischen Umsetzung einer Spezifikation in eine
  536. Implementierung wird ein Generator (ESTRA\**)
  537. .(f
  538. \**ESTRA -
  539. .b "E" "fficient"
  540. .b "S" "tructure"
  541. tree
  542. .b "TRA" "nsformation"
  543. .)f
  544. entwickelt.
  545. .lp
  546. Spezifikationssprache und Generator zusammen erm\*oglichen es,
  547. bei der Realisierung von
  548. Transformationen attributierter B\*aume von der Implementierung auf
  549. eine problemorientierte Spezifikation \*uberzugehen.
  550. .BP
  551. .SH 1 "M\*oglichkeiten zur Beschreibung von Transformationen"
  552. .lp
  553. Eine Transformation im Sinne dieser Arbeit ist jede Abbildung eines
  554. attributierten Baumes. Ob es sich beim Ergebnis einer solchen
  555. Abbildung wiederum um einen attributierten Baum handelt oder nicht
  556. spielt hierbei keine Rolle. Entscheidend ist einzig die Struktur der
  557. Eingabe.
  558. .lp
  559. Es werden drei unterschiedliche M\*oglichkeiten zur Beschreibung von
  560. Transformationen vorgestellt.
  561. .SH 2 "Attributierte Grammatiken"
  562. .lp
  563. Attributierte Grammatiken (AGs)\*([<\*([[Knu68\*(]]\*(>] werden im \*Ubersetzerbau
  564. vorwiegend eingesetzt, um die Semantische Analyse zu beschreiben. Sie
  565. werden aber auch zu Beschreibung der Codeerzeugung und -optimierung
  566. benutzt. AGs k\*onnen auch benutzt werden,
  567. um Transformationen zu beschreiben.
  568. .lp
  569. Normalerweise wird dabei so vorgegangen, da\*s das Ergebnis
  570. der Transformation durch den Wert eines Attributs an der Wurzel des
  571. Baumes dargestellt wird. Die Konsequenz dieser Vorgehensweise ist, da\*s
  572. das komplette Ergebnis der Transformation als Wert gespeichert werden
  573. mu\*s. Falls eine Ausgabe dieses Wertes erfolgen soll, mu\*s dies
  574. au\*serhalb des AG-Kalk\*uls beschrieben werden.
  575. Die Verwendung von Seiteneffekten zum sequentiellen Aufbau der
  576. Ausgabe ist mit diesem Ansatz nicht ohne weiteres m\*oglich,
  577. da die Reihenfolge, in der die einzelnen Attribute berechnet werden,
  578. nicht unmittelbar gesteuert werden kann.
  579. .lp
  580. Falls der Wunsch besteht, Seiteneffekte einzusetzen (z.B. zur
  581. Dateiausgabe), mu\*s die gew\*unschte Auswertungsreihenfolge
  582. durch Verwendung zus\*atzlicher Attribute mit entsprechenden
  583. Abh\*angigkeiten erzwungen werden. Diese komplizierte und aufwendige
  584. Art der Steuerung der Reihenfolge, die zudem recht unnat\*urlich ist,
  585. k\*onnte vermieden werden, wenn der sequentielle Ablauf durch
  586. imperative Programmierung unmittelbar beschrieben werden k\*onnte.
  587. .lp
  588. Transformationen realisieren in der Regel Abbildungen, die mehrere
  589. L\*osungen zulassen und einen sequentiellen Aufbau einer solchen
  590. L\*osung nahelegen. Transformationen sind also von Natur aus
  591. mehrdeutig und sequentiell. Es ist deshalb sinnvoll, zur Beschreibung
  592. einer Transformation eine mehrdeutige Spezifikation zu verwenden. Die
  593. Attributberechnung mu\*s allerdings auf alle F\*alle eindeutig sein.
  594. Mehrdeutigkeit in der Logik der Transformation mu\*s deshalb
  595. in der AG zur Beschreibung der Transformation durch zus\*atzliche
  596. Attribute und Berechnungen eindeutig gemacht werden.
  597. .lp
  598. Auf Grund der mehrdeutigen und sequentiellen Natur von
  599. Transformationen bieten AGs in ihrer Reinform keine ausreichenden
  600. Mittel, um Transformationen sinnvoll zu beschreiben.
  601. .SH 2 "Modifikation der Eingabe"
  602. .lp
  603. Eine weitere M\*oglichkeit, Transformationen durchzuf\*uhren besteht
  604. darin, die Ausgabe durch Modifikation der Eingabe zu erzeugen, wie es
  605. beispielsweise in\*([<\*([[MWW84\*(]]\*(>] beschrieben wird. Der Eingabebaum
  606. wird hier in einem iterativen Proze\*s so lange umgebaut,
  607. bis das Ergebnis der gew\*unschten Ausgabe entspricht.
  608. Die Transformation kann beschrieben werden, indem die einzelnen
  609. Schritte diese Proze\*ses durch Vorschriften festgelegt werden.
  610. Die Eleganz dieser Methode besteht darin, da\*s eine Transformation
  611. durch einzelne aufeinander aufbauende Schritte einfach und anschaulich
  612. beschrieben werden kann.
  613. .lp
  614. Die Reihenfolge und der Ort, auf den die einzelnen Vorschriften
  615. angewandt werden, kann die Anwendung weiterer Vorschriften und
  616. letztlich das gesamte Ergebnis entscheidend beeinflussen.
  617. Zur Beschreibung einer Transformation mu\*s deshalb neben den
  618. Vorschriften eine Strategie festgelegt werden, die Reihenfolge und Ort
  619. der Regelanwendungen bestimmt.
  620. .lp
  621. Es ist m\*oglich und i.a. sogar erw\*unscht, da\*s durch eine
  622. Modifikation eine weitere Modifikation erst m\*oglich wird. Das
  623. birgt jedoch die Gefahr in sich, da\*s der iterative Proze\*s nie
  624. endet, da immer weitere Modifikationen m\*oglich werden. Neben der
  625. Frage nach der Terminierung ergeben sich aus diesem Umstand Probleme
  626. bei der Absch\*atzung des Aufwands, der zur Durchf\*uhrung der
  627. Transformation erforderlich ist.
  628. .lp
  629. Bei einer Modifikation kann nicht ausgeschlossen werden, da\*s die
  630. Werte der Attribute des Baumes verloren gehen oder zumindest
  631. inkonsistent werden.
  632. Falls die einzelnen Vorschriften an Bedingungen \*uber die Attribute
  633. gekn\*upft werden sollen, ist es deshalb notwendig, unmittelbar nach
  634. jeder Modifikation eine Reattributierung durchzuf\*uhren.
  635. Wenn man auf eine Reattributierung verzichten will, verbleibt die
  636. M\*oglichkeit, die Modifikation der Eingabe einzusetzen, um
  637. nicht attributierte B\*aume zu transformieren.
  638. .SH 2 "Funktionale Abbildung"
  639. .lp
  640. Das Wesen einer funktionalen Abbildung eines attributierten Baumes
  641. besteht darin, da\*s der Ausgabewert neu berechnet wird,
  642. der alte Eingabebaum wird nur
  643. gelesen und bleibt somit unver\*andert. Das Pro\%blem der
  644. Reattributierung, wie es bei der Modifikation der Eingabe besteht,
  645. kann folglich nicht entstehen.
  646. .lp
  647. Durch eine imperative Beschreibung der Abbildung ist es unmittelbar
  648. m\*oglich, die Reihenfolge der Abarbeitung zu steuern, so da\*s eine
  649. sequentielle Ausgabe durch den Einsatz von Seiteneffekten ebenso
  650. m\*oglich ist wie der Aufbau eines neuen Baumes.
  651. .lp
  652. Eine mehrdeutige Beschreibung von Transformationen ist durch den
  653. Einsatz von Mustern und Kosten auf einfache und elegante Weise
  654. m\*oglich.
  655. .lp
  656. Das sequentielle und mehrdeutige Wesen von Transformationen kann mit
  657. dieser Methode unmittelbar beschrieben werden. Probleme, die durch den
  658. Einsatz von AGs oder die Modifikation der Eingabe entstehen, werden
  659. somit vermieden.
  660. .BP
  661. .SH 1 "Anforderungen an eine funktionale Beschreibung"
  662. .lp
  663. Im folgenden wird an Beispielen gezeigt, welche Anforderungen eine
  664. funktionale Beschreibung von Transformationen erf\*ullen mu\*s, und
  665. mit welchen Mitteln diese erf\*ullt werden k\*onnen.
  666. .lp
  667. Die einf\*uhrenden Beispiele aus dem Bereich der Codeerzeugung
  668. wurden ausgew\*ahlt, da sie sich eignen viele Probleme, die bei der
  669. Beschreibung von Transformationen entstehen, darzustellen. Gleichwohl
  670. sind dies nicht die typischen Anwendungsbeispiele, da f\*ur die
  671. Beschreibung der Codeerzeugung spezielle Sprachen und Werkzeuge\*([<\*([[Emm88\*(]]\*(>]
  672. existieren.
  673. .lp
  674. Die in den Beispielen verwendete Notation gibt einen Vorgeschmack auf
  675. die Spe\%zi\%fi\%ka\%tionssprache ESTRAL, die in Kapitel 5 ausf\*uhrlich
  676. beschrieben wird.
  677. .SH 2 "Abbildung der einzelnen Knoten"
  678. .lp
  679. Eine einfache Methode, Strukturb\*aume zu transformieren, besteht darin,
  680. alle Knoten eines Baumes zu besuchen und dabei das Ergebnis der
  681. Transformation sukzessive durch Abbildung der einzelnen Knoten zu
  682. erzeugen. W\*urde man eine feste Reihenfolge (z.B. Postfix) zum Besuch
  683. der einzelnen Knoten festlegen, so w\*urde es gen\*ugen, die
  684. Abbildung f\*ur jeden Knoten festzulegen. Diese einfache Methode
  685. w\*are bereits ausreichend, um Code zur Berechnung von arithmetischen
  686. Ausdr\*ucken auf einer Kellermaschine zu erzeugen (Abb. \n($1.1).
  687. .DS
  688. \fBTRANSFORMATION\fP T
  689.   A    {  Emit (Push A);    }
  690.   B    {  Emit (Push B);    }
  691.   C    {  Emit (Push C);    }
  692.   '*'    {  Emit (Multiply);    }
  693.   '+'    {  Emit (Add);        }
  694.  
  695. .PS
  696. .sp -1
  697. circlerad = 0.15i
  698. define lo X + (-0.3i, -0.4i) X
  699. define ro X + (0.3i, -0.4i) X
  700. [
  701. Plus:    circle invis "+"
  702. Mul:    circle invis "*" at Plus lo
  703. A:    circle invis "A" at Mul lo
  704. B:    circle invis "B" at Mul ro
  705. C:    circle invis "C" at Plus ro
  706.  
  707.   line from Plus.c to Mul.c chop
  708.   line from Plus.c to C.c chop
  709.   line from Mul.c to A.c chop
  710.   line from Mul.c to B.c chop
  711. ]
  712. boxht = 0.1i
  713. box invis "T" "\(->" with .w at last [].e
  714. box invis "Push A" "Push B" "Multiply" "Push C" "Add" with .w at last box.e
  715. .sp -0.5
  716. .PE
  717. .DE 1 "Transformation eines Strukturbaumes"
  718. Doch ist diese Methode nur begrenzt einsetzbar. Betrachten wir
  719. hierzu folgendes Beispiel (Abb. \n($1.2).
  720. .DS
  721. .PS
  722. .sp -1
  723. circlerad = 0.15i
  724. define lo X + (-0.3i, -0.4i) X
  725. define ro X + (0.3i, -0.4i) X
  726. [
  727. Ass:    circle invis ":="
  728. A1:    circle invis "A" at Ass lo
  729. Plus:    circle invis "+" at Ass ro
  730. A2:    circle invis "A" at Plus lo
  731. B:    circle invis "B" at Plus ro
  732.  
  733.   line from Ass.c to A1.c chop
  734.   line from Ass.c to Plus.c chop
  735.   line from Plus.c to A2.c chop
  736.   line from Plus.c to B.c chop
  737. ]
  738. .sp -0.5
  739. .PE
  740. .DE 2 "Strukturbaum einer Zuweisung"
  741. Hier w\*are es offensichtlich falsch, f\*ur den ersten Operanden der
  742. Zuweisung ein 'Push A' zu generieren. Hingegen ist dies f\*ur den
  743. ersten Operanden der Addition weiterhin erforderlich. Au\*serdem
  744. zeigt das Beispiel, da\*s eine feste Ablaufstrategie (wie Postfix) zum
  745. Besuch der einzelnen Knoten nicht immer brauchbar ist, denn bevor die
  746. Zuweisung erfolgen kann (Abb. \n($1.2), mu\*s die Summe berechnet werden.
  747. D.h. die Addition mit ihren Operanden A und B ist vor dem linken Operand
  748. der Zuweisung zu besuchen.
  749. .SH 2 "Steuerung der Reihenfolge"
  750. .lp
  751. Derartige Probleme k\*onnen gel\*ost werden, wenn man die Transformation
  752. in \fIFunktionen\fP gliedert und sowohl die Reihenfolge als auch
  753. die Art der durchzuf\*uhrenden Funktionen vom Kontext abh\*angig macht.
  754. .DS
  755. \fBTRANSFORMATION\fP CODE
  756. .HS
  757. \fBFUNCTION\fP PUSH
  758.   ':='    {   F1 (':='.ro); F2 (':='.lo);            }
  759.   A    {   Emit (Push A);                }
  760.   B    {   Emit (Push B);                }
  761.   '+'    {   F1 ('+'.lo); F1 ('+'.ro); Emit (Add);        }
  762. .HS
  763. \fBFUNCTION\fP STORE
  764.   A    {   Emit (Store A);                }
  765.   B    {   Emit (Store B);                }
  766.  
  767. .PS
  768. .sp -1
  769. circlerad = 0.15i
  770. define lo X + (-0.3i, -0.4i) X
  771. define ro X + (0.3i, -0.4i) X
  772. [
  773. Ass:    circle invis ":="
  774. Plus:    circle invis "+" at Ass ro
  775. A2:    circle invis "A" at Plus lo
  776. A1:    circle invis "A" at Ass lo
  777. B:    circle invis "B" at Plus ro
  778.  
  779.   line from Ass.c to A1.c chop
  780.   line from Ass.c to Plus.c chop
  781.   line from Plus.c to A2.c chop
  782.   line from Plus.c to B.c chop
  783. ]
  784. boxht = 0.1i
  785. box invis "CODE" "\(->" with .w at last [].e
  786. box invis "Push A" "Push B" "Add" "Store A" with .w at last box.e
  787. .sp -0.5
  788. .PE
  789. .DE 3 "Gliederung einer Transformation in mehrere Funktionen"
  790. In den Vorschriften (Abb. \n($1.3) erfolgt ein expliziter Aufruf von zum Teil
  791. verschiedenen Funktionen f\*ur die einzelnen Operanden (.lo
  792. bezeichnet hierbei den linken, .ro den rechten Operanden des angegebenen
  793. Knotens). Die Abarbeitungsreihenfolge ist nun explizit spezifiziert.
  794. .lp
  795. .SH 2 "Zugriff auf die Attribute"
  796. .lp
  797. Die Vorschriften zur Abbildung der Knoten A und B in Abb. \n($1.3 sind
  798. offensichtlich \*ahnlich. Dies liegt daran, da\*s es sich jeweils
  799. um einen Knoten handelt, der eine Variable darstellt. In solchen
  800. F\*allen sollte es m\*oglich sein, die Abbildung durch eine einzige Vorschrift
  801. zu beschreiben. Um das zu erreichen, fassen wir die Namen der Variablen
  802. als \fIAttribute\fP auf. Ein nunmehr attributierter Strukturbaum erh\*alt
  803. damit etwa folgende Gestalt (Abb. \n($1.4).
  804. .DS
  805. .PS
  806. .sp -1
  807. circlerad = 0.15i
  808. define lo X + (-0.3i, -0.4i) X
  809. define ro X + (0.3i, -0.4i) X
  810. [
  811. Ass:    circle invis ":="
  812. Plus:    circle invis "+" at Ass ro
  813. A2:    circle invis "V\s-2\d[N=A]\u\s+2" at Plus lo
  814. A1:    circle invis "V\s-2\d[N=A]\u\s+2" at Ass lo
  815. B:    circle invis "V\s-2\d[N=B]\u\s+2" at Plus ro
  816.  
  817.   line from Ass.c to A1.c chop
  818.   line from Ass.c to Plus.c chop
  819.   line from Plus.c to A2.c chop
  820.   line from Plus.c to B.c chop
  821. ]
  822. .sp -0.5
  823. .PE
  824. .DE 4 "Attributierter Strukturbaum einer Zuweisung"
  825. An Stelle der Knoten A und B erscheinen nur noch Knoten vom Typ
  826. V (Variable), die ein Attribut N (Name der Variablen) besitzen, das hier
  827. die Werte A und B annimmt. Die Beschreibung der Transformation nimmt
  828. dann folgende Form an (Abb. \n($1.5).
  829. .DS
  830. \fBTRANSFORMATION\fP CODE
  831. .HS
  832. \fBFUNCTION\fP PUSH
  833.   ':='    {   F1 (':='.ro); F2 (':='.lo);            }
  834.   V    {   Emit (Push V.N);                }
  835.   '+'    {   F1 ('+'.lo); F1 ('+'.ro); Emit (Add);        }
  836. .HS
  837. \fBFUNCTION\fP STORE
  838.   V    {   Emit (Store V.N);                }
  839. .DE 5 "Beschreibung der Transformation eines attributierten Strukturbaumes"
  840. .SH 2 "Berechnung eines synthetisierten Attributs"
  841. .lp
  842. Bei der bisher betrachteten Kellermaschine werden Ergebnisse eines
  843. Teilausdrucks auf dem Keller abgelegt. Hat man es dagegen mit einer
  844. Registermaschine zu tun, wird man Zwischenergebnisse in einem
  845. Register ablegen. Um nun Code f\*ur eine Operation zu erzeugen, ist
  846. es erforderlich, zu wissen in welchen Registern die Zwischenergebnisse
  847. stehen.
  848. .lp
  849. Diese Information kann zur Verf\*ugung gestellt werden, wenn
  850. gleichzeitig mit der Transformation eine \fIS-Attributierung\fP
  851. (Attributierung, bei der nur synthetisierte Attribute berechnet
  852. werden) durchgef\*uhrt wird. Da die Attribute bei der Transformation
  853. unmittelbar verarbeitet werden, ist es nicht notwendig, sie
  854. explizit im Baum zu speichern, es gen\*ugt, wenn die
  855. Attribute unmittelbar nach der Transformation eines Teilbaums zur
  856. Verf\*ugung stehen. Dies wird erreicht, indem die Attribute als
  857. Ergebnisse der einzelnen Funktionen dargestellt werden.
  858. .lp
  859. In Abb. \n($1.6 wird dieser Mechanismus benutzt um festzuhalten, in welchem
  860. Register das Zwischenergebnis steht. Die Funktion Reg, die die Transformation
  861. durchf\*uhrt, liefert dieses Register als Ergebnis.
  862. .DS
  863. \fBTRANSFORMATION\fP T
  864. .HS
  865. \fBFUNCTION\fP Reg: register
  866.   '+'    {
  867.     i := Reg ('+'.lo);
  868.     j := Reg ('+'.ro);
  869.     Emit (ADD Rj, Ri);
  870.     FreeReg (j);        (* Register j ist nun wieder frei *)
  871.     RETURN i;
  872.     }
  873. .HS
  874.   '*'    {
  875.     i := Reg ('*'.lo);
  876.     j := Reg ('*'.ro);
  877.     Emit (MULS Rj, Ri);
  878.     FreeReg (j);        (* Register j ist nun wieder frei *)
  879.     RETURN i;
  880.     }
  881. .HS
  882.   V    {
  883.     i := GetReg ();        (* Beschaffe Register f\*ur Zwischenergebnis *)
  884.     Emit (MOVE V.N@, Ri);
  885.     RETURN i;
  886.     }
  887.  
  888. .PS
  889. .sp -1
  890. circlerad = 0.15i
  891. define lo X + (-0.3i, -0.4i) X
  892. define ro X + (0.3i, -0.4i) X
  893. [
  894. Plus:    circle invis "+"
  895. Mul:    circle invis "*" at Plus lo
  896. A:    circle invis "V\s-2\d[N=A]\u\s+2" at Mul lo
  897. C:    circle invis "V\s-2\d[N=C]\u\s+2" at Plus ro
  898. B:    circle invis "V\s-2\d[N=B]\u\s+2" at Mul ro
  899.  
  900.   line from Plus.c to Mul.c chop
  901.   line from Plus.c to C.c chop
  902.   line from Mul.c to A.c chop
  903.   line from Mul.c to B.c chop
  904. ]
  905. boxht = 0.1i
  906. box invis "T" "\(->" with .w at last [].e
  907. box invis "MOVE A@, R1" \
  908.       "MOVE B@, R2" \
  909.       "MULS R2, R1" \
  910.       "MOVE C@, R2" \
  911.       "ADD R2, R1" \
  912.       with .w at last box.e
  913. .sp -0.5
  914. .PE
  915. .DE 6 "S-Attributierung"
  916. Die Registervergabe erfolgt 'on the fly'. Um das Beispiel einfach
  917. zu halten, wurde davon ausgegangen, da\*s immer gen\*ugend Register
  918. vorhanden sind, was z.B. dann der Fall ist, wenn bei der Erzeugung von
  919. Zwischencode Pseudoregister an Stelle der realen Register verwendet
  920. werden.
  921. .lp
  922. Das Beispiel in Abb. \n($1.6 zeigt, da\*s es nun prinzipiell m\*oglich ist,
  923. eine Transformation zu beschreiben, die Code f\*ur eine Registermaschine
  924. liefert. Allerdings ist der generierte Code schlecht im Vergleich zu
  925. der in Abb. \n($1.7 angegebenen Transformation.
  926. .DS
  927. .PS
  928. .sp -1
  929. circlerad = 0.15i
  930. define lo X + (-0.3i, -0.4i) X
  931. define ro X + (0.3i, -0.4i) X
  932. [
  933. Plus:    circle invis "+"
  934. Mul:    circle invis "*" at Plus lo
  935. A:    circle invis "V\s-2\d[N=A]\u\s+2" at Mul lo
  936. C:    circle invis "V\s-2\d[N=C]\u\s+2" at Plus ro
  937. B:    circle invis "V\s-2\d[N=B]\u\s+2" at Mul ro
  938.  
  939.   line from Plus.c to Mul.c chop
  940.   line from Plus.c to C.c chop
  941.   line from Mul.c to A.c chop
  942.   line from Mul.c to B.c chop
  943. ]
  944. boxht = 0.1i
  945. box invis "\(->" with .w at last [].e
  946. box invis "MOVE A@, R1" \
  947.       "MULS B@, R1" \
  948.       "ADD C@, R1" \
  949.       with .w at last box.e
  950. .sp -0.5
  951. .PE
  952. .DE 7 "optimierte Transformation eines arithmetischen Ausdrucks"
  953. .SH 2 "Muster"
  954. .lp
  955. Offensichtlich ist es nicht erforderlich, die zweiten Operanden der
  956. Addition und Multiplikation in ein Hilfsregister zu laden, wenn es sich
  957. dabei wie hier um eine (direkt zugreifbare) Variable handelt. Da wir
  958. aber bislang immer nur einzelne Knoten abgebildet haben, konnte bei
  959. der Transformation der Addition (bzw. Multiplikation) nicht erkannt
  960. werden, ob es sich beim rechten Operanden um eine Variable handelt.
  961. Im folgenden werden wir deshalb an Stelle von einzelnen Knoten (kleine)
  962. Ausschnitte m\*oglicher Strukturb\*aume, sogenannte \fIMuster\fP, verwenden,
  963. um eine Transformation festzulegen.
  964. .lp
  965. Diese Muster m\*ussen nun auf den Teil des Strukturbaums passen, der
  966. mit dem aktuellen (d.h. dem zu transformierenden) Knoten beginnt. Die
  967. Muster werden durch ihre geklammerte Prefixform dargestellt. Um
  968. Operanden zu beschreiben, die nicht eindeutig festgelegt sind, k\*onnen
  969. Nichtterminale verwendet werden. So wird z.B. in Abb. \n($1.8 das
  970. Nichtterminal expr verwendet, wenn beliebige Ausdr\*ucke
  971. erlaubt sind. Um in den Anweisungen leichter auf den Baum zugreifen zu
  972. k\*onnen, k\*onnen die Namen der Knoten und Nichtterminale, die im
  973. Muster stehen, verwendet werden. Falls es hierbei zu Mehrdeutigkeit
  974. kommt, kann diese durch freigew\*ahlte Bezeichner, die im Muster mit
  975. angegeben werden, aufgel\*ost werden (siehe e1 und e2 in Abb. \n($1.8).
  976. .lp
  977. Mit Hilfe von Mustern sollte es nun m\*oglich sein, eine Transformation
  978. zu beschreiben, die in der Lage ist, den optimalen Code von Abb. \n($1.7 zu
  979. erzeugen. Dazu erweitern wir die Beschreibung von Abb. \n($1.6
  980. um zwei Vorschriften, die die Spezialf\*alle behandeln, da\*s es sich beim
  981. rechten Operanden einer Addition bzw. Multiplikation um eine (direkt
  982. zugreifbare) Variable handelt.
  983. .SH 2 "Mehrdeutigkeit und Kosten"
  984. .lp
  985. Offensichtlich mu\*s die dadurch entstandene Beschreibung mehrdeutig
  986. sein, da ja die alte M\*oglichkeit der nicht optimalen Codeerzeugung
  987. weiterhin besteht. Damit die optimale L\*osung ausgew\*ahlt werden kann,
  988. werden Kosten f\*ur die Vorschriften eingef\*uhrt.
  989. Mit Hilfe dieser Kosten lassen sich dann die Kosten der Transformation
  990. als Summe der Kosten aller angewandten Vorschriften berechnen. Im Falle einer
  991. Mehrdeutigkeit wird nun die optimale L\*osung, d.h. die L\*osung mit
  992. den geringsten Kosten ausgew\*ahlt.
  993. .lp
  994. Wenn die L\*ange des erzeugten Codes zur Festlegung der Kosten
  995. herangezogen wird, ergibt sich f\*ur unser Beispiel die Beschreibung
  996. von Abb. \n($1.8.
  997. .DS
  998. \fBTRANSFORMATION\fP T
  999. .HS
  1000. \fBFUNCTION\fP Reg: Register
  1001.   '+' (e1: expr, e2: expr)    \fBCOST\fP 2
  1002.             {
  1003.             i := Reg (e1); j := Reg (e2);
  1004.             Emit (ADD Rj, Ri);
  1005.             FreeReg (j); RETURN i;
  1006.             }
  1007. .HS
  1008.   '*' (e1: expr, e2: expr)    \fBCOST\fP 2
  1009.             {
  1010.             i := Reg (e1); j := Reg (e2);
  1011.             Emit (MULS Rj, Ri);
  1012.             FreeReg (j); RETURN i;
  1013.             }
  1014. .HS
  1015.   V ()            \fBCOST\fP 4
  1016.             {
  1017.             i := GetReg ();
  1018.             Emit (MOVE V.N@, Ri);
  1019.             RETURN i;
  1020.             }
  1021. .HS
  1022.   '+' (expr, V ())        \fBCOST\fP 4
  1023.             {    (* rechter Operand ist eine Variable *)
  1024.             i := Reg (expr);
  1025.             Emit (ADD V.N@, Ri)
  1026.             RETURN i;
  1027.             }
  1028. .HS
  1029.   '*' (expr, V ())        \fBCOST\fP 4
  1030.             {    (* rechter Operand ist eine Variable *)
  1031.             i := Reg (expr);
  1032.             Emit (MULS V.N@, Ri)
  1033.             RETURN i;
  1034.             }
  1035. .DE 8 "Mehrdeutigkeit und Kosten zur Optimierung einer Transformation"
  1036. Betrachten wir nochmals die L\*osungen von Abb. \n($1.6 und
  1037. \n($1.7 und berechnen jeweils die Kosten. Im ersten Fall
  1038. ergibt sich eine Summe von 16, im zweiten (optimierten) Fall sind es
  1039. nur 12. Die Einf\*uhrung von Kosten liefert also offensichtlich das
  1040. gew\*unschte Ergebnis.
  1041. .SH 2 "Bedingungen"
  1042. .lp
  1043. Attribute des Strukturbaumes wurden bislang nur benutzt, um die bei der
  1044. Codeerzeugung notwendigen konkreten Werte (z.B. Adressen) zur
  1045. Verf\*ugung zu stellen.
  1046. Es kann aber auch vorkommen, da\*s eine Vorschrift nur dann verwendet
  1047. werden darf, wenn Attributwerte eine spezielle \fIBedingung\fP
  1048. erf\*ullen.
  1049. .DS
  1050. .PS
  1051. .sp -1
  1052. circlerad = 0.15i
  1053. define lo X + (-0.3i, -0.4i) X
  1054. define ro X + (0.3i, -0.4i) X
  1055. Mul:    circle invis "*"
  1056. V:    circle invis "V\s-2\d[N=A]\u\s+2" at Mul lo
  1057. C:    circle invis "C\s-2\d[V=4]\u\s+2" at Mul ro
  1058. line from Mul.c to V.c chop
  1059. line from Mul.c to C.c chop
  1060. .sp -0.5
  1061. .PE
  1062. .DE 9 "Produkt einer Variablen mit einer Konstanten (Zweierpotenz)"
  1063. Um beispielsweise das Produkt einer Variablen und der Konstanten 4 (Abb. \n($1.9)
  1064. zu berechnen, gen\*ugt es, den Wert der Variablen um zwei Bin\*arstellen
  1065. nach links zu verschieben. Dieses Verfahren geht aber offensichtlich
  1066. nicht f\*ur beliebige Konstanten, sondern nur f\*ur solche, die eine
  1067. Zweierpotenz darstellen. Um dies durch eine Vorschrift beschreiben zu
  1068. k\*onnen, f\*uhren wir die M\*oglichkeit ein, eine Vorschrift mit einer
  1069. Bedingung (condition) zu verkn\*upfen (Abb. \n($1.10).
  1070. .DS
  1071.   '*' (expr, C ())        \fBCOST\fP 2
  1072.             \fBCONDITION\fP { IsPowerOf2 (C.V) }
  1073.             {
  1074.             i := Reg (expr);
  1075.             d := Log2 (C.V);
  1076.             Emit (ASL #d, Ri)
  1077.             RETURN i;
  1078.             }
  1079. .DE 10 "Vorschrift mit einer Bedingung"
  1080. Durch die Kombination Mehrdeutigkeit, Bedingungen und Kosten ist es
  1081. auf einfache Weise m\*oglich, Transformatoren zu beschreiben, die in
  1082. der Lage sind, eine optimierte Abbildung durchzuf\*uhren.
  1083. .SH 2 "Mehrfachtransformation"
  1084. .lp
  1085. Eine weiteres Mittel bei der Beschreibung von Transformationen, das in
  1086. den bisherigen Beispielen noch nicht verwendet wurde, ist die
  1087. \fIMehrfachtransformation\fP. Eine Mehr\%fach\%trans\%formation liegt dann vor,
  1088. wenn ein Teilbaum mehrmals auf die selbe (Abb. \n($1.13) oder auf unterschiedliche
  1089. Weise transformiert wird.
  1090. .DS
  1091. \fBTRANSFORMATION\fP T
  1092. .HS
  1093. \fBFUNCTION\fP Copy: tree
  1094.   WHILE (expr, stmt)    {
  1095.             e1 := Copy (expr);
  1096.             s  := Copy (stmt);
  1097.             e2 := Copy (expr);
  1098.             e3 := MakeNOT (e2);
  1099.             r  := MakeREPEAT (s, e3);
  1100.             RETURN MakeIF (e1, r);
  1101.              }
  1102.  
  1103. .PS
  1104. .sp -1
  1105. circlerad = 0.15i
  1106. define lo X + (-0.3i, -0.4i) X
  1107. define ro X + (0.3i, -0.4i) X
  1108. define o X + (0i, -0.4i) X
  1109. [
  1110. Whi:    circle invis "WHILE"
  1111. Exp:    circle invis "expr" at Whi lo
  1112. Sta:    circle invis "stmt" at Whi ro
  1113.  
  1114.   line from Whi.c to Exp.c chop
  1115.   line from Whi.c to Sta.c chop
  1116. ]
  1117. boxht = 0.1i
  1118. box invis "Copy" "\(->" with .w at last [].e + (0.2i, 0i)
  1119. [
  1120. If:    circle invis "IF"
  1121. Exp1:    circle invis "Copy(expr)  " at If lo
  1122. Rep:    circle invis "REPEAT" at If ro
  1123. Sta:    circle invis "Copy(stmt)" at Rep lo
  1124. Not:    circle invis "NOT" at Rep ro
  1125. Exp2:    circle invis "Copy(expr)" at Not o
  1126.  
  1127.   line from If.c to Exp1.c chop
  1128.   line from If.c to Rep.c chop
  1129.   line from Rep.c to Sta.c chop
  1130.   line from Rep.c to Not.c chop
  1131.   line from Not.c to Exp2.c chop 0.1i
  1132. ] with .w at last box.e
  1133. .sp -0.5
  1134. .PE
  1135. .DE 11 "Transformation einer While-Schleife"
  1136. Eine While-Schleife kann durch eine Repeat-Schleife ersetzt werden,
  1137. wenn letztere in eine bedingte Anweisung (IF) eingeschlossen wird.
  1138. Der Ausdruck (expr) der Bedingung mu\*s hierzu offensichtlich
  1139. dupliziert werden. Abb. \n($1.11 zeigt, wie dies durch eine
  1140. Mehrfachtransformation realisiert wird.
  1141. .lp
  1142. Eine andere Form der Mehrfachtransformation ist die mehrfache
  1143. Transformation eines Strukturbaumes auf unterschiedliche Weise. Bei
  1144. dieser Form der Mehrfachtransformation werden verschiedene Funktionen
  1145. auf einen Teilbaum angewandt.
  1146. .lp
  1147. .SH 2 "Synthetisierte und vererbte Attribute"
  1148. .lp
  1149. Bei komplexen Transformation reicht eine S-Attributierung, wie sie 2.4.
  1150. eingef\*uhrt, nicht aus.
  1151. .lp
  1152. Ein Beispiel f\*ur eine solche Transformation ist die Normierung
  1153. des Strukturbaumes eines regul\*aren Ausdrucks. Ein regul\*arer
  1154. Ausdruck ist ein Ausdruck, der den folgenden Regeln gehorcht:
  1155. .np
  1156. jeder Bezeichner (Identifier) ist ein regul\*arer Ausdruck
  1157. .np
  1158. wenn R1 und R2 regul\*are Ausdr\*ucke sind, dann sind auch:
  1159.   R1 '\(or' R2    (Alternative)
  1160.   R1 R2    (Sequenz)
  1161.   (R1)
  1162.   R1 '*'    (Wiederholung)
  1163. .br
  1164. Regul\*are Ausdr\*ucke.
  1165. .lp
  1166. Da es sich bei der Sequenz (das selbe gilt f\*ur die Alternative) um
  1167. eine assoziative Operation handelt, gibt es unterschiedliche
  1168. M\*oglichkeiten zur Darstellung des selben regul\*aren Ausdrucks in
  1169. Form eines Strukturbaumes. Durch die unn\*otige Verwendung von
  1170. Klammern oder die automatische Erzeugung von regul\*aren
  1171. Ausdr\*ucken ist es unter Umst\*anden unvermeidlich, da\*s diese
  1172. verschiedenen Strukturb\*aume tats\*achlich aufgebaut werden.
  1173. .DS
  1174. .PS
  1175. .sp -1
  1176. circlerad = 0.15i
  1177. define lo X + (-0.45i, -0.4i) X
  1178. define llo X + (-0.9i, -0.4i) X
  1179. define ro X + (0.45i, -0.4i) X
  1180. define rro X + (0.9i, -0.4i) X
  1181. define o X + (0i, -0.4i) X
  1182. [
  1183. boxht = 0.1i
  1184. box invis "(ab)((c*)b)"
  1185. ]
  1186. boxht = 0.1i
  1187. box invis "\(==" with .w at last [].e
  1188. [
  1189. S1:    circle invis "SEQ"
  1190. S2:    circle invis "SEQ" at S1 llo
  1191. S3:    circle invis "SEQ" at S1 rro
  1192. I1:    circle invis "   IDENT\s-2\d[Name=a]\u\s+2" at S2 lo
  1193. I2:    circle invis "       IDENT\s-2\d[Name=b]\u\s+2" at S2 ro
  1194. R:    circle invis "" "*" at S3 lo
  1195. I3:    circle invis "     IDENT\s-2\d[Name=c]\u\s+2" at R o
  1196. I4:    circle invis "   IDENT\s-2\d[Name=b]\u\s+2" at S3 ro
  1197.  
  1198. line from S2.c to S1.c chop 0.25i
  1199. line from S3.c to S1.c chop 0.25i
  1200. line from I1.c to S2.c chop
  1201. line from I2.c to S2.c chop
  1202. line from R.c to S3.c chop 0.1i
  1203. line from I3.c to R.c chop
  1204. line from I4.c to S3.c chop
  1205. ] with .w at last box.e
  1206. .PE
  1207. .PS
  1208. [
  1209. boxht = 0.1i
  1210. box invis "(((ab)c*)b)"
  1211. ]
  1212. boxht = 0.1i
  1213. box invis "\(==" with .w at last [].e
  1214. [
  1215. S1:    circle invis "SEQ"
  1216. S2:    circle invis "SEQ" at S1 llo
  1217. S3:    circle invis "SEQ" at S2 llo
  1218. I1:    circle invis "     IDENT\s-2\d[Name=a]\u\s+2" at S3 llo
  1219. I2:    circle invis "   IDENT\s-2\d[Name=b]\u\s+2" at S3 ro
  1220. R:    circle invis "" "*" at S2 ro
  1221. I3:    circle invis "       IDENT\s-2\d[Name=c]\u\s+2" at R o
  1222. I4:    circle invis "   IDENT\s-2\d[Name=b]\u\s+2" at S1 ro
  1223.  
  1224. line from S2.c to S1.c chop 0.25i
  1225. line from S3.c to S2.c chop 0.25i
  1226. line from I1.c to S3.c chop 0.25i
  1227. line from I2.c to S3.c chop
  1228. line from R.c to S2.c chop 0.1i
  1229. line from I3.c to R.c chop
  1230. line from I4.c to S1.c chop
  1231. ] with .w at last box.e
  1232. .sp -0.5
  1233. .PE
  1234. .DE 12 "verschiedene Darstellungen des selben regul\*aren Ausdrucks"
  1235. Um solche Strukturb\*aume (Abb. \n($1.12) zu normieren, d.h. f\*ur
  1236. eine einheitliche Darstellung der regul\*aren Ausdr\*ucke zu sorgen,
  1237. geht man zweckm\*a\*sigerweise wie folgt vor:
  1238. .np
  1239. Nicht assoziative und un\*are Operatoren werden eins zu eins
  1240. abgebildet.
  1241. .np
  1242. Beim Antreffen eines assoziativen Operators werden alle
  1243. darunterliegenden Knoten mit demselben Operator zusammengefa\*st.
  1244. Die darunterliegenden Teilb\*aume werden der Reihe nach
  1245. transformiert. Dabei wird ein normierter (zur Liste entarteter) Baum
  1246. mit dem aktuellen Operator aufgebaut, dessen Bl\*atter durch die
  1247. Transformationsergebnisse der Teilb\*aume gebildet werden.
  1248. .lp
  1249. Um dies zu realisieren reicht eine
  1250. S-Attributierung deshalb nicht aus, weil die B\*aume zur Normierung
  1251. nicht nur hochgereicht, d.h. \fIsynthetisiert\fP, sondern auch nach unten
  1252. gegeben d.h. \fIvererbt\fP werden m\*ussen.
  1253. .lp
  1254. Um diese Vererbung beschreiben zu k\*onnen, ordnen wir einer
  1255. Funktion zus\*atzlich zum Ergebnisattribut noch weitere
  1256. vererbte und synthetisierte Attribute zu. Diese Attribute m\*ussen
  1257. beim Aufruf einer Funktion neben dem zu transformierenden
  1258. Strukturbaum, der immer das erste Argument bildet, \*ubergeben werden.
  1259. .DS
  1260. .ta 5c 7c
  1261. \fBTRANSFORMATION\fP OrderTree
  1262.  
  1263. \fBFUNCTION\fP Order: tTree
  1264.   Alt (r1: RegExpr, r2: RegExpr)        { RETURN OrderAlt (r2, Order (r1)); }
  1265.   Seq (r1: RegExpr, r2: RegExpr)        { RETURN OrderSeq (r2, Order (r1)); }
  1266.   Star (RegExpr)        { RETURN MakeSTAR (Order (RegExpr)); }
  1267.   Ident ()        { RETURN MakeIdent (Ident.Name); }
  1268.  
  1269. \fBFUNCTION\fP OrderSeq    List: tTree \(mi> : tTree
  1270.   Seq (r1: RegExpr, r2: RegExpr)    \fBCOST\fP 1    { RETURN OrderSeq (r2, OrderSeq (r1, List)); }
  1271.   Ident ()    \fBCOST\fP 1    { RETURN MakeSEQ (List, MakeIdent (Ident.Name)); }
  1272.   RegExpr    \fBCOST\fP 2    { RETURN MakeSEQ (List, Order (RegExpr)); }
  1273.  
  1274. \fBFUNCTION\fP OrderAlt    List: tTree \(mi> : tTree
  1275.   Alt (r1: RegExpr, r2: RegExpr)    \fBCOST\fP 1    { RETURN OrderAlt (r2, OrderAlt (r1, List)); }
  1276.   Ident ()    \fBCOST\fP 1    { RETURN MakeALT (List, MakeIdent (Ident.Name)); }
  1277.   RegExpr    \fBCOST\fP 2    { RETURN MakeALT (List, Order (RegExpr)); }
  1278. .DE 13 "Normierung eines regul\*aren Ausdruckes durch Transformation"
  1279. Die Funktion OrderSeq sammelt die gesamte Sequenz ein und baut mit
  1280. Hilfe des vererbten Attributs List (vererbte Attribute stehen links
  1281. von Pfeil ('\(mi>'), synthetisierte rechts)
  1282. und dem Ergebnisattribut sukzessive
  1283. den normierten Baum f\*ur die Sequenz auf. Die allgemeine Vorschrift (die
  1284. Vorschrift mit dem Muster 'RegExpr') wird aufgrund der Kosten nur f\*ur die
  1285. \*ubrigen Operatoren (nicht f\*ur die Sequenz) gew\*ahlt. Sie
  1286. st\*o\*st dann wiederum die Funktion Order f\*ur den
  1287. aktuellen Knoten an. Die Funktion OrderAlt arbeitet entsprechend
  1288. f\*ur Alternativen.
  1289. .BP
  1290. .SH 1 "Begriffe"
  1291. .lp
  1292. Bevor weiter auf die Spezifikation und die Implementierung von Transformationen
  1293. eingegangen wird, m\*ussen einige zentrale Begriffe gekl\*art werden.
  1294. .SH 2 "Baumgrammatik"
  1295. .lp
  1296. Eine Baumgrammatik ist eine spezielle kontextfreie Grammatik,
  1297. die hier eingesetzt wird, um die Struktur der zu transformierenden B\*aume zu
  1298. beschreiben.
  1299. .lp
  1300. Eine Baumgrammatik ist ein Viertupel G = (C, N, \(*P, Z) mit
  1301. .np
  1302. C = Menge der Klassen
  1303. .np
  1304. N = Menge der Knoten
  1305. .np
  1306. \(*P = Menge der Produktionen \(ib C \(mu (C \(cu N C*)
  1307. .np
  1308. Z = Menge der Startsymbole \(ib C
  1309. .lp
  1310. Die Klassen C einer Baumgrammatik entsprechen den Nichtterminalen,
  1311. die Knoten den Terminalen einer gew\*ohnlichen kontextfreien Grammatik.
  1312. .lp
  1313. Bei den Produktionen \(*P einer Baumgrammatik werden zwei Typen unterschieden:
  1314. .np
  1315. Kettenproduktion:
  1316. .br
  1317. c\*<0\*> \(-> c\*<1\*> mit c\*<0\*>, c\*<1\*> \(mo C
  1318. .np
  1319. Knotenproduktion:
  1320. .br
  1321. c\*<0\*> \(-> n (c\*<1\*>, ..., c\*<m\*>)
  1322. mit
  1323. n \(mo N, c\*<0\*>, c\*<1\*>, ..., c\*<m\*> \(mo C
  1324. .lp
  1325. Die \fIKettenproduktion\fP ersetzt eine Klasse c\*<0\*> durch eine
  1326. Klasse c\*<1\*>; c\*<0\*> hei\*st Oberklasse von c\*<1\*>.
  1327. .lp
  1328. Bei der \fIKnotenproduktion\fP werden ein Knoten n aufgebaut, und die
  1329. Klassen c\*<1\*>, ..., c\*<m\*> seiner S\*ohne festgelegt.
  1330. Da die rechte Seite einer Knotenproduktion einen Knoten n beschreibt wird
  1331. sie auch als Knotenbeschreibung (oder kurz Beschreibung) des Knotens
  1332. n bezeichnet.
  1333. Die Klammern in den Knotenproduktionen haben keine Bedeutung, sie
  1334. erh\*ohen jedoch die Lesbarkeit und erm\*oglichen au\*serdem die
  1335. Unterscheidung von Ketten- und Knotenproduktionen aufgrund der Darstellung.
  1336. .lp
  1337. Damit eine Grammatik f\*ur unsere Zwecke brauchbar ist, m\*ussen weitere
  1338. Forderungen erf\*ullt werden:
  1339. .np
  1340. Zyklenfreiheit:
  1341. .br
  1342. c\*<0\*>
  1343. \(-> c\*<1\*>
  1344. \(-> ...
  1345. \(-> c\*<m\*>
  1346. \(RA
  1347. c\*<0\*> \(!= c\*<m\*>
  1348. .br
  1349. die Kettenproduktionen m\*ussen azyklisch sein
  1350. .np
  1351. Eindeutigkeit der Oberklasse:
  1352. .br
  1353. c\*<1\*> \(-> c\*<0\*>,
  1354. c\*<2\*> \(-> c\*<0\*>
  1355. \(RA
  1356. c\*<1\*> = c\*<2\*>
  1357. .br
  1358. jede Klasse besitzt h\*ochstens eine Oberklasse:
  1359. .np
  1360. Feste Wertigkeit:
  1361. .br
  1362. c\*<0\*> \(-> n (c\*<1\*>, ..., c\*<m\*>),
  1363. c\*'\*<0\*> \(-> n (c\*'\*<1\*>, ..., c\*'\*<m'\*>) 
  1364. \(RA
  1365. m = m'
  1366. .br
  1367. die Anzahl der S\*ohne ist f\*ur alle Knotenbeschreibungen eines
  1368. Knotens identisch
  1369. .np
  1370. Eindeutigkeit der Knotenbeschreibung innerhalb einer Klasse:
  1371. .br
  1372. c\*<0\*> \(-> n (c\*<1\*>, ..., c\*<m\*>),
  1373. c\*<0\*> \(-> n (c\*'\*<1\*>, ..., c\*'\*<m\*>) 
  1374. \(RA
  1375. c\*<1\*> = c\*'\*<1\*>, ..., c\*<m\*> = c\*'\*<m\*>,
  1376. .br
  1377. ein Knoten darf in einer Klasse nur einmal beschrieben sein
  1378. .np
  1379. Prinzip der Hauptbeschreibung:
  1380. .br
  1381. \(fa n \(mo N:
  1382. \(te c\*<0\*> \(-> n (c\*<1\*>, ..., c\*<m\*>) \(mo \(*P:
  1383. .br
  1384. c\*'\*<0\*> \(-> n (c\*'\*<1\*>, ..., c\*'\*<m\*>) \(mo \(*P
  1385. \(RA
  1386. c\*<0\*> \(-> ... \(-> c\*'\*<0\*>,
  1387. c\*<1\*> \(-> ... \(-> c\*'\*<1\*>, ...,
  1388. c\*<m\*> \(-> ... \(-> c\*'\*<m\*>
  1389. .br
  1390. f\*ur jeden Knoten existiert eine Beschreibung, aus der alle andern
  1391. Beschreibungen des selben Knotens abgeleitet werden k\*onnen.
  1392. .np
  1393. Reduziertheit:
  1394. .br
  1395. Von der Baumgrammatik wird verlangt, da\*s sie reduziert ist, d.h.
  1396. alle Klassen und Knoten m\*ussen von den Startsymbolen aus erreichbar
  1397. sein und alle Klassen m\*ussen terminalisierbar sein.
  1398. .lp
  1399. Die Eigenschaften erleichtern zum einen die Darstellung und den Umgang mit
  1400. der Baumgrammatik, andererseits sind sie notwendig damit die B\*aume
  1401. vern\*unftig implementiert werden k\*onnen.
  1402. .DS
  1403. .ta 1c 2c 3c 4.5c
  1404. G = (C, N, \(*P, Z)
  1405.  
  1406. C = {expr, const, index}
  1407. N = {'+', Const, Ident}
  1408. \(*P = {    expr    \(->    const,
  1409.     expr    \(->    index,
  1410.     expr    \(->    '+'    (expr, expr),
  1411.     const    \(->    Const    (),
  1412.     const    \(->    '+'    (const, const),
  1413.     index    \(->    Ident    () }
  1414. Z = {expr}
  1415. .DE 1 "Baumgrammatik f\*ur arithmetische Ausdr\*ucke"
  1416. Abb. \n($1.1 zeigt eine Baumgrammatik f\*ur arithmetische Ausdr\*ucke,
  1417. die diese Forderungen erf\*ullt. Die Grammatik ist zyklenfrei (1).
  1418. Die Klassen const und index besitzen beide die eindeutige Oberklasse
  1419. expr (2). Beide Beschreibungen von '+' haben die Wertigkeit
  1420. zwei (3) und liegen in unterschiedlichen Klassen (4). Die Produktion
  1421. expr \(-> '+' (expr, expr) legt die Hauptbeschreibung fest. Die zweite
  1422. Knotenproduktion f\*ur '+' (const \(-> '+' (const, const)) kann aus
  1423. der ersteren abgeleitet werden (5). Die Grammatik ist reduziert (6).
  1424. .SH 2 "Muster"
  1425. .lp
  1426. Wenn man ausgehend von einer Klasse endlich viele Produktionen anwendet,
  1427. entsteht ein Ausdruck, den wir als Muster bezeichnen. Muster werden verwendet,
  1428. um die Menge aller aus ihnen ableitbaren B\*aumen darzustellen.
  1429. .lp
  1430. Wenn ein Baum aus einem Muster abgeleitet werden kann, dann
  1431. \fIpa\*st\fP das Muster auf diesen Baum.
  1432. .lp
  1433. Bei der Darstellung von Mustern ist es zul\*assig, Klassen wegzulassen,
  1434. wenn diese aufgrund der Hauptbeschreibung ohnehin festgelegt sind.
  1435. Diese Freiheit hat zur Folge, da\*s es verschiedene Muster gibt, die
  1436. die selbe Menge von B\*aumen darstellen.
  1437. .lp
  1438. Abb. \n($1.2 zeigt ein Beispiel. Die Doppelpunkte in den Mustern dienen
  1439. als Platzhalter f\*ur die weggelassenen Klassen. Der Doppelpunkt stellt
  1440. das sogenannte \fIallgemeine Muster\fP, das immer pa\*st, dar.
  1441. .DS
  1442. .ta 1c 3.5c
  1443. \&'+'    (:, :)    \fI(normiert)\fP
  1444. \&'+'    (expr, :)
  1445. \&'+'    (:, expr)
  1446. \&'+'    (expr, expr)
  1447. .DE 2 "verschiedene Muster zur Darstellung der selben Mengen von B\*aumen"
  1448. Da in der Grammatik von Abb. \n($1.1 \fIIdent\fP der einzige Knoten ist,
  1449. der aus der Klasse \fIindex\fP abgeleitet werden kann, stellen die beiden
  1450. Muster von Abbildung \n($1.3 ebenfalls die selbe Menge von B\*aumen dar.
  1451. .DS
  1452. .ta 1c 3.5c
  1453. index        \fI(normiert)\fP
  1454. Ident    ()
  1455. .DE 3 "verschiedene Muster zur Darstellung der selben Mengen von B\*aumen"
  1456. .lp
  1457. Der Grund f\*ur die M\*oglichkeit, ein Menge von B\*aumen durch
  1458. verschiedene Muster darzustellen, ist also zum einen die
  1459. M\*oglichkeit, die Klasse des Sohnes nicht zu
  1460. spezifizieren, zum anderen die Eigenschaft, da\*s ein
  1461. Knoten mitunter bereits durch eine Klasse eindeutig festgelegt ist.
  1462. .lp
  1463. Um diese unterschiedliche Darstellungen zu vermeiden,
  1464. wird der Begriff des \fInormierten Musters\fP eingef\*uhrt. Ein Muster
  1465. hei\*st normiert, wenn es durch die zwei oben genannten
  1466. Eigenschaften (Klasse der S\*ohne mu\*s nicht spezifiziert werden,
  1467. Knoten ist durch Klasse festgelegt) nicht vereinfacht werden kann.
  1468. .lp
  1469. Eine dritte M\*oglichkeit besteht, wenn die Oberklasse einer Klasse
  1470. keine eigenen Knotenbeschreibungen enth\*alt und f\*ur keine
  1471. weitere Klasse Oberklasse ist. In diesem Fall kann aus der Oberklasse
  1472. nichts abgeleitet werden, was nicht auch aus der Klasse selbst entstehen
  1473. k\*onnte. Somit sind diese beide Klassen bei der Darstellung eines
  1474. Musters vollkommen austauschbar.
  1475. .lp
  1476. In der Praxis wird diese M\*oglichkeit in der Regel nicht auftreten,
  1477. da man normalerweise versuchen wird, mit einer m\*oglichst einfachen
  1478. Grammatik auszukommen und deshalb das Auftreten \*aquivalenter Klassen
  1479. vermieden wird.
  1480. .SH 2 "Beziehungen zwischen Mustern"
  1481. .lp
  1482. Um die Beziehungen zwischen zwei Mustern beschreiben zu k\*onnen,
  1483. werden die folgenden Begriffe und Notationen verwendet.
  1484. .np
  1485. p\*<1\*> = p\*<2\*>
  1486. .br
  1487. Zwei Muster sind \fIgleich\fP, falls gilt, da\*s entweder beide Muster
  1488. passen oder keines der Muster pa\*st.
  1489. .np
  1490. p\*<1\*> < p\*<2\*>
  1491. .br
  1492. Ein Muster p\*<1\*> ist \fIkleiner\fP als p\*<2\*>, wenn das Passen von
  1493. p\*<1\*> aus dem Passen von p\*<2\*> folgt und die beiden Muster
  1494. nicht gleich sind.
  1495. .np
  1496. p\*<1\*> > p\*<2\*>
  1497. .br
  1498. Ein Muster p\*<1\*> ist \fIgr\*o\*ser\fP als p\*<2\*>, wenn
  1499. p\*<2\*> kleiner als p\*<1\*> ist.
  1500. .np
  1501. p\*<1\*> \(or\(or p\*<2\*>
  1502. .br
  1503. Ein Muster p\*<1\*> ist \fIinkonsistent\fP zu p\*<2\*>, wenn
  1504. es keinen Baum gibt, auf den sowohl p\*<1\*> als auch p\*<2\*>
  1505. pa\*st.
  1506. .np
  1507. p\*<1\*> \(ap p\*<2\*>
  1508. .br
  1509. Ein Muster p\*<1\*> ist \fIunabh\*angig\fP von p\*<2\*>, wenn
  1510. p\*<1\*> und p\*<2\*> unabh\*angig voneinander passen k\*onnen.
  1511. .lp
  1512. Die Begriffe sind\*([<\*([[HoO82\*(]]\*(>]
  1513. entnommen. Dort werden jedoch keine
  1514. unterschiedlichen Klassen betrachtet, wie es hier geschieht.
  1515. Statt dessen gibt es lediglich ein Symbol, das f\*ur beliebige
  1516. B\*aume steht.
  1517. .lp
  1518. Die Einf\*uhrung von Klassen hat zur Folge, da\*s es aufwendiger
  1519. wird zu berechnen, welche Be\%zie\%hung zwischen zwei Mustern gilt.
  1520. .lp
  1521. Betrachten wir den Fall, da\*s es sich bei den beiden
  1522. Mustern jeweils nur um eine Klasse handelt. Die Frage nach der
  1523. Beziehung zwischen den beiden Mustern ist dann gleichbedeutend zu
  1524. entscheiden, ob die Sprachen, die durch zwei unterschiedliche
  1525. Baumgrammatiken definiert werden, identisch sind (gleich), ob eine Sprache
  1526. eine Untermenge der anderen ist (kleiner/gr\*o\*ser), ob der Schnitt
  1527. der beiden Sprachen leer ist (inkonsistent) oder ob es sich um Quermengen
  1528. handelt (unabh\*angig).
  1529. .lp
  1530. In der Praxis ist es jedoch m\*oglich, mit einer N\*aherungsl\*osung
  1531. auszukommen. Diese N\*aherungsl\*osung entsteht, indem in einzelnen
  1532. F\*allen in Kauf genommen wird, da\*s zwei Muster als unabh\*angig
  1533. betrachtet werden, obwohl eine der anderen Beziehungen gilt.
  1534. Dieser Fehler kann in Kauf genommen werden, da er nur in pathologischen
  1535. F\*allen eintritt und keine Folgefehler verursacht. 
  1536. .lp
  1537. Im Al\%go\%rith\%mus zur Berechnung der Beziehung zwischen zwei
  1538. (normierten) Mustern (Abb. \n($1.5) werden folgende Hilfsfunktionen
  1539. verwendet (Abb. \n($1.4).
  1540. .DS
  1541. .ta 1.5c 6c 14.5c
  1542. Ident    (pat: tPattern): tIdent    (* liefert den Bezeichner der Wurzel von pat    *)
  1543. Type    (id: tIdent): tType    (* liefert den Typ (class oder node) von id    *)
  1544. Arity    (node: tIdent): INTEGER    (* liefert die Wertigkeit des Knotens    *)
  1545. Classes    (pat: tPattern): tSet    (* liefert die Klassen zu denen pat geh\*ort    *)
  1546. Subclasses (class: tIdent): tSet    (* liefert die Unterklassen von class    *)
  1547. ClassesOfNode (node: tIdent): tSet    (* liefert alle Klassen in denen node beschrieben ist    *)
  1548. NodesOfClass (class: tIdent): tSet    (* liefert alle Knoten die aus class hervorgehen k\*onnen    *)
  1549. .DE 4 "Hilfsfunktionen zur Berechnung der Beziehung zwischen zwei Mustern"
  1550. .DS
  1551. .ta 9c 13c
  1552. Relation (pat1, pat2: tPattern): tRelation;
  1553. .HS
  1554. \fBif\fP (pat1 = NoPat) & (pat2 = NoPat) \fBthen return\fP equal    (* pat1 = pat2    *)
  1555. \fBif\fP (pat1 = NoPat) \fBthen return\fP less    (* pat1 < pat2    *)
  1556. \fBif\fP (pat2 = NoPat) \fBthen return\fP greater    (* pat1 > pat2    *)
  1557. .HS
  1558. id1 := Ident (pat1)
  1559. type1 := Type (id1)
  1560. id2 := Ident (pat2)
  1561. type2 := Type (id2)
  1562. .HS
  1563. \fBif\fP (type1 = class) & (type2 = class) \fBthen\fP    (* A *)
  1564.   \fBif\fP (id1 = id2) \fBthen return\fP equal    (* pat1 = pat2    *)
  1565.   \fBelsif\fP (id1 \(mo Classes (pat2)) \fBthen return\fP less    (* pat1 < pat2    *)
  1566.   \fBelsif\fP (id2 \(mo Classes (pat1)) \fBthen return\fP greater    (* pat1 > pat2    *)
  1567.   \fBif\fP NodesOfClass (id1) \(ca NodesOfClass (id2) \(eq \(es \fBthen\fP
  1568.     \fBreturn\fP inconsistent    (* pat1 \(ap pat2    *)
  1569.   \fBelse return\fP independent    (* pat1 \(or\(or pat2    *)
  1570. .HS
  1571. \fBelsif\fP (type1 = class) \fBthen\fP    (* B *)
  1572.   \fBif\fP (id1 \(mo Classes (pat2)) \fBthen return\fP less    (* pat1 < pat2    *)
  1573.   \fBelse\fP
  1574.     common := (Subclasses (id1)\(cu{id1}) \(ca ClassesOfNode (id2)
  1575.     \fBif\fP common = \(es \fBthen return\fP inconsistent    (* pat1 \(or\(or pat2    *)
  1576.     \fBelse return\fP independent    (* pat1 \(ap pat2    *)
  1577. .HS
  1578. \fBelsif\fP (type2 = class) \fBthen\fP    (* C *)
  1579.   \fBif\fP (id2 \(mo Classes (pat1)) \fBthen return\fP greater    (* pat1 > pat2    *)
  1580.   \fBelse\fP
  1581.     common :=  (Subclasses (id2)\(cu{id2}) \(ca ClassesOfNode (id1)
  1582.     \fBif\fP common = \(es \fBthen return\fP inconsistent    (* pat1 \(or\(or pat2    *)
  1583.     \fBelse return\fP independent    (* pat1 \(ap pat2    *)
  1584. .DB
  1585. \fBelse\fP    (* D *)
  1586.   \fBif\fP id1 = id2 \fBthen\fP
  1587.     relation := equal;    (* up to now: pat1 = pat2    *)
  1588.     \fBfor\fP pos := 1 to Arity (id1) \fBdo\fP
  1589.       \fBcase\fP Relation (Son (pat1, pos), Son (pat2, pos)) \fBof\fP
  1590.       | equal:
  1591.       | independent:
  1592.             relation := independent    (* now: pat1 \(ap pat2    *)
  1593.       | inconsistent:
  1594.           \fBreturn\fP inconsistent    (* pat1 \(or\(or pat2    *)
  1595.       | greater:
  1596.           \fBif\fP relation = equal
  1597.             \fBthen\fP relation := greater    (* now: pat1 > pat2    *)
  1598.           \fBelsif\fP relation = less
  1599.             \fBthen\fP relation := independent    (* now: pat1 \(ap pat2    *)
  1600.       | less:
  1601.           \fBif\fP relation = equal
  1602.             \fBthen\fP relation := less    (* now: pat1 < pat2    *)
  1603.           \fBelsif\fP relation = greater
  1604.             \fBthen\fP relation := independent    (* now: pat1 \(ap pat2    *)
  1605.     \fBreturn\fP relation
  1606.   \fBelse return\fP inconsistent    (* pat1 \(or\(or pat2    *)
  1607. .DE 5 "Algorithmus zur Berechnung der Beziehung von zwei Mustern"
  1608. Zu Beginn des Algorithmus Relation (Abb. \n($1.5) werden
  1609. die einfachen F\*alle behandelt, die entstehen, wenn eines der
  1610. Muster oder beide Muster leer sind (NoPat). Falls hier keine Entscheidung
  1611. f\*allt, ist sichergestellt, da\*s beide Muster eine Klasse oder
  1612. einen Knoten als Wurzel enthalten.
  1613. .lp
  1614. Handelt es sich um zwei Klassen (A), so gilt Gleichheit, falls die Klassen
  1615. identisch sind. Trifft dies nicht zu wird gepr\*uft, ob ein Muster aus
  1616. der Klasse des anderen abgeleitet werden kann und somit kleiner als
  1617. dieses ist. Zuletzt wird noch gepr\*uft ob es Knoten gibt, die aus
  1618. beiden Klassen hervorgehen k\*onnen, die beiden Klassen werden dann als
  1619. unabh\*angig bezeichnet. Bei dieser Festlegung handelt es sich um
  1620. einen N\*aherung, denn tats\*achlich kann hier (in pathologischen
  1621. F\*allen) auch jede andere Beziehung gelten. Im \*ubrigen sind
  1622. die Klassen und damit die Muster mit Sicherheit inkonsistent.
  1623. .lp
  1624. Bei den beiden n\*achsten F\*allen (B, C) liegen jeweils eine Klasse und
  1625. ein Knoten als Wurzel vor. Kann das Muster mit dem Knoten als Wurzel
  1626. aus der Klasse abgeleitet werden, steht die Beziehung fest. Im anderen
  1627. Falle wird gepr\*uft ob es \*uberhaupt Muster gibt, die aus der
  1628. Klasse abgeleitet werden k\*onnen und den Knoten als Wurzel haben, denn
  1629. dann werden die Muster als unabh\*angig betrachtet. Ansonsten
  1630. sind die beiden Muster inkonsistent.
  1631. .lp
  1632. Falls beide Muster einen Knoten als Wurzel haben (D), gibt es zwei
  1633. M\*oglichkeiten. Sind die beiden Knoten identisch, m\*ussen die
  1634. S\*ohne betrachtet werden. Hierzu wird ein Hilfsvariable
  1635. (relation) auf gleich (equal) initialisiert. Diese Hilfsvariable stellt
  1636. die Beziehung der bereits be\%trach\%te\%ten Teile der beiden Muster dar. In
  1637. Abh\*angigkeit von den Beziehungen der S\*ohne wird der Wert von
  1638. relation gegebenenfalls angepa\*st, bis sp\*atestens nach
  1639. Betrachten aller S\*ohne das Ergebnis feststeht.
  1640. Sind die beiden Knoten hingegen verschieden, steht sofort Inkonsistenz
  1641. fest.
  1642. .BP
  1643. .SH 1 "Spezifikation von Transformationen mit ESTRAL"
  1644. .lp
  1645. Im folgenden wird die Eingabesprache zur Spezifikation von
  1646. Transformationen beschrieben.
  1647. .SH 2 "Reservierte W\*orter und Symbole"
  1648. .lp
  1649. Die folgende Liste enth\*alt die reservierten W\*orter in ESTRAL:
  1650. .(l I
  1651. .b
  1652. .sz -2
  1653. BEGIN, CLOSE, CONDITION, COSTS, DECLARE, EXPORT,
  1654. FUNCTION, GLOBAL, GRAMMAR, TRANSFORMATION
  1655. .sz +2
  1656. .)l
  1657. Die Symbole
  1658. .(l I
  1659. .b
  1660. .sz -2
  1661. (     )     {     }     ,     .     /     :     ;     =     \(or     \(mi>
  1662. .sz +2
  1663. .)l
  1664. werden als Operatoren und Begrenzer verwendet.
  1665. .SH 2 "Bezeichner"
  1666. .lp
  1667. Bezeichner (identifiers) sind Folgen aus Buchstaben (letters),
  1668. Ziffern (digits) und dem Unterstreichungsstrich (underscore). Ein
  1669. Bezeichner mu\*s immer mit einem Buchstaben beginnen.
  1670. Wenn reservierte W\*orter als Bezeichner verwendet werden, sind sie mit
  1671. einem '\e' als Fluchtsymbol zu maskieren. Dieses
  1672. Fluchtsymbol, das auch vor jedem anderen Bezeichner stehen darf, ist
  1673. jedoch nicht Bestandteil des Bezeichners, es dient lediglich zur
  1674. Unterscheidung von Schl\*usselw\*ortern und Bezeichnern.
  1675. .lp
  1676. Abb. \n($1.1 zeigt einen regul\*aren Ausdruck, der den Aufbau eines
  1677. Bezeichners beschreibt.
  1678. .DS
  1679. .ta 3c
  1680. ident =    ['\e'] letter (letter \(or digit \(or '_')*
  1681. .DE 1 "regul\*arer Ausdruck f\*ur Bezeichner"
  1682. Beispiele f\*ur korrekte Bezeichner sind:
  1683. .(l I
  1684. .sz -2
  1685. Bezeichner, Doppel_Wort, \eSTOP, END, \eBEGIN, A2, b4
  1686. .sz +2
  1687. .)l
  1688. Die folgende Zeichenfolgen sind hingegen keine g\*ultigen Bezeichner:
  1689. .(l I
  1690. .sz -2
  1691. BEGIN    \fI(Schl\*usselw\*orter sind nicht erlaubt)\fP
  1692. \e\eEND    \fI(nur ein ' \e' ist erlaubt)\fP
  1693. 4A    \fI(Ziffer darf nicht am Anfang stehen)\fP
  1694. A-Z    \fI(Bindestrich ist nicht erlaubt)\fP
  1695. .sz +2
  1696. .)l
  1697. Bei der Verwendung von Bezeichnern ist au\*serdem zu beachten, da\*s
  1698. sie vom Generator verwendet werden, um
  1699. Bezeichner f\*ur das Zielprogramm zu bilden. Einschr\*ankungen, die in
  1700. der Zielsprache f\*ur Bezeichner gelten, sollten deshalb unbedingt
  1701. auch eingehalten werden.
  1702. .lp
  1703. Beispiele f\*ur solche Einschr\*ankungen sind das Verbot von '_' in
  1704. Bezeichnern der Programmiersprache Modula-2\*([<\*([[Wir85\*(]]\*(>] oder die Beschr\*ankung
  1705. der signifikanten L\*ange von Bezeichnern in C\*([<\*([[KeR83\*(]]\*(>].
  1706. .SH 2 "Zeichenketten"
  1707. .lp
  1708. Zeichenketten (strings) sind in Anf\*uhrungszeichen ('"')  oder
  1709. Apostrophe ("'") eingeschlossene Zeichenfolgen. Die Zeichenfolge darf
  1710. alle Zeichen au\*ser dem Zeilenende und dem Begrenzer selbst enthalten.
  1711. .lp
  1712. .SH 2 "Zahlen"
  1713. .lp
  1714. Da nur positive ganze Zahlen ben\*otigt werden, gen\*ugt es, Zahlen
  1715. (numbers) als Folgen von Ziffern aufzufassen.
  1716. .SH 2 "Kommentare"
  1717. .lp
  1718. Kommentare k\*onnen in den von Modula-2 und C gewohnten Formen
  1719. geschrieben werden, so da\*s es m\*oglich ist, Kommentare innerhalb und
  1720. au\*serhalb von Quelltexten in der selben Weise zu schreiben.
  1721. .SH 2 "Quelltext"
  1722. .lp
  1723. Zur Darstellung von Bedingungen, Kosten, Vereinbarungen und Anweisungen
  1724. wird Quelltext (source text) der
  1725. Zielsprache verwendet. Der Quelltext wird in geschweifte Klammern
  1726. eingeschlossen. Da dieser Text nicht immer direkt \*ubernommen
  1727. werden kann, sondern zum Teil umgesetzt werden mu\*s, sind einige
  1728. Regeln zu beachten, die es dem Generator erlauben, den Quelltext zu
  1729. analysieren.
  1730. .lp
  1731. Kommentare, Zeichenketten und Bezeichner, die im Quelltext stehen,
  1732. werden als Einheiten betrachtet, die nicht weiter untergliedert werden.
  1733. Geschweifte Klammern d\*urfen innerhalb des Quelltextes nur paarweise
  1734. auftreten, damit das Ende des Quelltextes erkennbar ist. Klammern
  1735. innerhalb von Kommentaren und Zeichenketten werden hierbei
  1736. nat\*urlich nicht mitgez\*ahlt.
  1737. .lp
  1738. Obwohl diese Regeln so gew\*ahlt wurden, da\*s sie beim Schreiben
  1739. von Quelltexten m\*oglichst wenig einschr\*anken, gibt es einige
  1740. Fehlerquellen, auf die man achten sollte.
  1741. .lp
  1742. So darf folgendes korrekte C-Programmfragment keinesfalls in dieser Form
  1743. geschrieben werden.
  1744. .(l
  1745. .sz -2
  1746. { i = 3 * (*p + i); }
  1747. .sz +2
  1748. .)l
  1749. Die Folge w\*are, da\*s ein (nicht geschlossener)
  1750. Modula-2-Kommentar erkannt w\*urde. Doch kann dieses Problem leicht
  1751. beseitigt werden, indem man ein Leerzeichen zur Trennung der Klammer
  1752. und des Adre\*soperators benutzt.
  1753. .(l
  1754. .sz -2
  1755. { i = 3 * ( *p + i) }
  1756. .sz +2
  1757. .)l
  1758. Nun kann nicht mehr f\*alschlich ein Kommentar erkannt werden.
  1759. .lp
  1760. Weitere Probleme k\*onnen bei Zeichenketten in C entstehen,
  1761. da sich die Festlegung der Schreibweise von Zeichenketten an den
  1762. Konventionen von Modula-2 orientierte.
  1763. .(l
  1764. .sz -2
  1765. { c = '\e''; }
  1766. { printf ("\e""; }
  1767. .sz +2
  1768. .)l
  1769. Solche Eingaben f\*uhren zu Fehlermeldungen, da jeweils eine nicht
  1770. geschlossene Zeichenkette erkannt wird.
  1771. .SH 2 "Transformation"
  1772. .lp
  1773. Die Beschreibung einer Transformation (Abb. \n($1.2) besteht
  1774. aus einer \fIBaumgrammatik\fP (grammar), zur Beschreibung
  1775. der Struktur der zu transformierenden B\*aume und mehreren
  1776. \fIFunktionen\fP (function), die die Abbildung beschreiben.
  1777. Die \fIIntegration\fP des generierten Programms in eine Umgebung
  1778. wird in einem weiteren Abschnitt (integration) beschrieben.
  1779. .DS
  1780. .TS
  1781. llll.
  1782. transformation    \(eq    \fBTRANSFORMATION\fP
  1783.           ident    \fIName der Transformation\fP
  1784.           integration    \fIIntegration\fP
  1785.           grammar    \fIBaumgrammatik\fP
  1786.           function *    \fIFunktionen\fP
  1787. .TE
  1788. .DE 2 "Transformation"
  1789. Um mehrere Transformationen unterscheiden zu k\*onnen, wird jeder
  1790. Transformation ein \fIName\fP zugeordnet.
  1791. .SH 2 "Baumgrammatik"
  1792. .lp
  1793. Die Baumgrammatik wird benutzt, um die Struktur der zul\*assigen
  1794. B\*aume zu beschreiben und bildet die Grundlage f\*ur alle
  1795. Konsistenzpr\*ufungen (vgl. 4.1.) denen die Eingabe unterzogen wird.
  1796. .DS
  1797. .TS
  1798. llll.
  1799. grammar    \(eq    \fBGRAMMAR\fP
  1800.           ident    \fIName der Grammatik\fP
  1801.           class *    \fIBeschreibung der Klassen\fP
  1802. .TE
  1803. .DE 3 "Baumgrammatik"
  1804. Der \fIName der Grammatik\fP wird in der Implementierung benutzt, um
  1805. das Modul, das die B\*aume realisiert, zu bezeichnen. Die
  1806. eigentliche Grammatik wird mit Hilfe der \fIKlassen\fP beschrieben.
  1807. .SH 2 "Klassen"
  1808. .lp
  1809. Klassen werden durch einen Bezeichner, dem ein Gleichheitszeichen
  1810. folgt, definiert. Zusammen mit den Klassen werden auch die Produktionen
  1811. der Baumgrammatik festgelegt. Die Kettenproduktionen k\*onnen
  1812. aufgrund des Oberklassenprinzips (vgl. Kapitel 4) durch die optionale
  1813. Angabe einer
  1814. Oberklasse beschrieben werden. Die Knotenproduktionen werden beschrieben,
  1815. indem alle Knotenbeschreibungen bei der zugeh\*origen Klasse
  1816. aufgez\*ahlt werden.
  1817. .DS
  1818. .TS
  1819. llll.
  1820. class    \(eq    [ ident '\(mi>' ]    \fIBezeichner der Oberklasse\fP
  1821.           ident '='    \fIBezeichner der Klasse\fP
  1822.           node *    \fIKnotenbeschreibungen\fP
  1823. .TE
  1824. .DE 4 "Klassen"
  1825. .SH 2 "Knoten"
  1826. .lp
  1827. Die Knotenbeschreibung ordnet dem Knoten einen \fINamen\fP in Form einer
  1828. Zeichenkette oder eines Bezeichners zu und z\*ahlt seine S\*ohne auf.
  1829. .DS
  1830. .TS
  1831. llll.
  1832. node    \(eq    '\(or' (string \(or ident)    \fIName des Knotens\fP
  1833.           [ ':' ident ]    \fIBezeichner des Knotens (siehe Hauptbeschreibung)\fP
  1834.           '(' [ son \(or\(or ',' ] ')'    \fIS\*ohne\fP
  1835. .TE
  1836. .DE 5 "Knoten"
  1837. Beispiele:
  1838. .(l I
  1839. .ta 5 10 15 20
  1840. .sz -2
  1841. | '+'    : Plus    (e1: expr, e2: expr)
  1842. | ':='    : Asgn    (index, expr)
  1843. | While        (expr, then: stats, else: stats)
  1844. | Const        ()
  1845. .sz +2
  1846. .)l
  1847. .SH 2 "S\*ohne"
  1848. .lp
  1849. Um den Sohn eines Knotens festzulegen, wird seine \fIKlasse\fP angegeben.
  1850. .DS
  1851. .TS
  1852. llll.
  1853. son    \(eq    [ ident ':' ]    \fIName des Sohnes (nur in der Hauptbeschreibung)\fP
  1854.           ident    \fIKlasse des Sohnes\fP
  1855. .DE 6 "S\*ohne"
  1856. .TE
  1857. Beispiele:
  1858. .(l I
  1859. .sz -2
  1860. expr
  1861. e1: expr
  1862. const
  1863. .sz +2
  1864. .)l
  1865. .he ''%''
  1866. .bp 1
  1867. .he '\s-2\fRInhaltsverzeichnis\fP\s+2''%'
  1868. .lp
  1869. .b Inhaltsverzeichnis
  1870. .lp
  1871. .sp
  1872. .xp
  1873. .BP 28
  1874. .SH 2 "Hauptbeschreibung" 5 12
  1875. .lp
  1876. Aufgrund des in Kapitel 4.1. geforderten Prinzips der
  1877. Hauptbeschreibung, mu\*s f\*ur jeden Knoten eine Hauptbeschreibung
  1878. existieren. Diese Hauptbeschreibung hat neben ihrer Funktion als
  1879. Knotenproduktion der Baumgrammatik die Aufgabe, die Implementierung des
  1880. Knotens zu beschreiben. In der Hauptbeschreibung eines Knotens
  1881. werden deshalb der \fIBezeichner des Knotens\fP (Abb. \n($1.5) und die
  1882. \fINamen der Klassen\fP (Abb. \n($1.6) festgelegt. Diese werden in der
  1883. Implementierung verwendet, um auf den Knoten, dessen Attribute und
  1884. S\*ohne zuzugreifen und die Art des Knotens festzustellen (vgl. Kapitel 9.1.).
  1885. Falls keine explizite Festlegung erfolgt, wird der Bezeichner des Knotens
  1886. mit seinem Namen und die Namen der S\*ohne mit den Klassen
  1887. gleichgesetzt.
  1888. Klassen gleichgesetzt.
  1889. .SH 2 "Funktionen"
  1890. .lp
  1891. Die Funktionen beschreiben die Abbildung, die durch die Transformation
  1892. realisiert werden soll.
  1893. .lp
  1894. Die Beschreibung einer \fIFunktion\fP (function) (Abb. \n($1.7)
  1895. umfa\*st den \fINamen\fP (ident) der Funktion, die Beschreibung der
  1896. \fIvererbten\fP und \fIsynthetisierten Attribute\fP (attributes),
  1897. die Festlegung des \fIErgebnistyps\fP und des \fIDefinitionsbereichs\fP,
  1898. sowie \fIVorschriften\fP (directive) zur Durchf\*uhrung der Transformation.
  1899. .DS
  1900. .TS
  1901. llll.
  1902. Function    \(eq    \fBFUNCTION\fP
  1903.           ident    \fIName der Funktion\fP
  1904.           [ attributes '\(mi>' attributes ]    \fIvererbte und synthetisierte Attribute\fP
  1905.           [ ':' type ]    \fIErgebnistyp\fP
  1906.           domain    \fIDefinitionsbereich\fP
  1907.           directive *    \fIVorschriften zur Beschreibung der Funktion\fP
  1908. .TE
  1909. .DE 7 "Funktionen"
  1910. Die Transformation wird durchgef\*uhrt, indem die erste Funktion auf
  1911. den zu transformierenden Baum angewandt wird. Der Definitionsbereich
  1912. der Transformation kann deshalb mit dem Definitionsbereich der ersten
  1913. Funktion gleichgesetzt werden.
  1914. .lp
  1915. Die Vollst\*andigkeit wird in der in Kapitel 8 beschriebenen Weise
  1916. \*uberpr\*uft.
  1917. .SH 2 "Typen"
  1918. .lp
  1919. Typen (Abb. \n($1.8) werden durch einen Bezeichner wie z.B.
  1920. .ip
  1921. \s-2\&INTEGER, REAL, BOOLEAN\s+2
  1922. .lp
  1923. beschrieben.
  1924. .lp
  1925. Um einen qualifizierten Import, wie er in Modula-2
  1926. m\*oglich ist, zu beschreiben, kann ein weitere Bezeichner
  1927. verwendet werden, um das Modul festzulegen.
  1928. Damit sind auch Angaben der Form
  1929. .ip
  1930. \s-2\&SYSTEM.TSIZE, Sets.tSet, IO.WriteS\s+2
  1931. .lp
  1932. m\*oglich.
  1933. .DS
  1934. .TS
  1935. llll.
  1936. type    \(eq    [ ident '.' ]    \fIAngabe des Moduls zur Qualifikation\fP
  1937.           ident     \fIBezeichner des Typs\fP
  1938. .TE
  1939. .DE 8 "Typen"
  1940. .SH 2 "Attribute"
  1941. .lp
  1942. Die Angabe der Attribute ist optional. Einzelne Attribute werden
  1943. durch einen Bezeichner und einen Typ beschrieben. Um mehrere Attribute
  1944. des selben Typs zu beschreiben, werden die Bezeichner, durch Komma
  1945. getrennt, aufgez\*ahlt. Wenn Attribute mit unterschiedlichen Typen
  1946. beschrieben werden, sind die einzelnen Beschreibungen durch
  1947. Strichpunkte zu trennen.
  1948. .DS
  1949. .TS
  1950. llll.
  1951. attributes    \(eq    [ ( (ident \(or\(or ','    \fIListe von Bezeichnern\fP
  1952.           ':' type)    \fIAngabe des Typs\fP
  1953.           \(or\(or ';' ) ]    \fI mehrere solche Listen durch ';' getrennt\fP
  1954. .TE
  1955. .DE 9 "Attribute"
  1956. .lp
  1957. Beispiel:
  1958. .ip
  1959. \s-2\&A: INTEGER; B,C: REAL\s+2
  1960. .SH 2 "Definitionbereich"
  1961. .lp
  1962. Der \fIDefinitionsbereich\fP (domain) einer Funktion wird
  1963. festgelegt, indem die \fIKlassen\fP (ident), f\*ur die die Funktion
  1964. definiert ist, aufgez\*ahlt werden.
  1965. .DS
  1966. .TS
  1967. llll.
  1968. domain    \(eq    '/' ident \(or\(or ',' '/'    \fIListe von Klassen\fP
  1969. .TE
  1970. .DE 10 "Definitionsbereich"
  1971. Beispiel:
  1972. .(l I
  1973. .sz -2
  1974. / stats, expr /
  1975. .sz +2
  1976. .)l
  1977. Der Definitionsbereich der ersten Funktion legt au\*serdem die
  1978. Startsymbole fest und bildet somit die Basis f\*ur die
  1979. \*Uberpr\*ufung der Reduziertheit der Grammatik (vgl. 4.1.).
  1980. .SH 2 "Vorschriften"
  1981. .lp
  1982. Die \fIVorschriften\fP (directive), die die Abbildungen im einzelnen
  1983. beschreiben, bestehen im einfachsten Falle aus einem \fIMuster\fP
  1984. (pattern), das festlegt, auf welche (Teil-) B\*aume die Vorschrift
  1985. angewandt werden kann und \fIAnweisungen\fP (instructions), die
  1986. festlegen, wie der betreffende (Teil-) Baum behandelt werden mu\*s.
  1987. .DS
  1988. .TS
  1989. llll.
  1990. directive    \(eq    pattern    \fIMuster\fP
  1991.           [ condition ]    \fIBedingung\fP
  1992.           [ costs ]    \fIKosten\fP
  1993.           [ declarations ]    \fIlokale Vereinbarungen\fP
  1994.           instructions    \fIAnweisungen\fP
  1995. .TE
  1996. .DE 11 "Vorschriften"
  1997. .SH 2 "Muster"
  1998. .lp
  1999. Das Muster beschreibt einen Ausschnitt des Baumes, der in den
  2000. Anweisungen bearbeitet wird. Mit Hilfe der Selektoren kann in den
  2001. Vorschriften auf die entsprechenden Knoten des Strukturbaumes
  2002. zugegriffen werden. Die Selektoren
  2003. werden, falls sie nicht explizit angegeben sind, aus den Namen der
  2004. Knoten bzw. Klassen abgeleitet. Falls es hierbei zu Mehrdeutigkeit
  2005. kommt, liegt ein Fehler vor. Die automatische Erzeugung eines
  2006. Selektors wird unterdr\*uckt, wenn ein Doppelpunkt angegeben wird,
  2007. dem kein Bezeichner vorangestellt ist. Wenn auf spe\%zielle Knoten in den
  2008. Anweisungen nicht zugegriffen werden mu\*s, k\*onnen durch die
  2009. Unterdr\*uckung Mehrdeutigkeiten vermieden werden.
  2010. .DS
  2011. .TS
  2012. llll.
  2013. pattern    \(eq    [ [ ident ] ':' ]    \fISelektor\fP
  2014.           (ident \(or string)    \fIName des Knotens\fP
  2015.           '(' [ pattern \(or\(or ',' ] ')'    \fIS\*ohne\fP
  2016.     \(or    [ ident ] ':'    \fISelektor\fP
  2017.           [ ident ]    \fIBezeichner der Klasse\fP
  2018.     \(or    ident    \fISelektor und Bezeichner der Klasse\fP
  2019. .TE
  2020. .DE 12 "Muster"
  2021. Beispiele:
  2022. .(l I
  2023. .sz -2
  2024. \&'+' (e1:, e2:)
  2025. \&':=' (index, expr)
  2026. If (expr, then:, else:)
  2027. :'+' (:'+' (e1: const, e2: const), e3:)
  2028. expr
  2029. const
  2030. .sz +2
  2031. .)l
  2032. .SH 2 "Anweisungen"
  2033. .DS
  2034. .TS
  2035. llll.
  2036. instructions    \(eq    '{' source_text '}'
  2037. .TE
  2038. .DE 13 "Anweisungen"
  2039. .lp
  2040. Die \fIAnweisungen\fP (instructions) sind der Kern jeder Vorschrift,
  2041. sie werden vom Transformator ausgef\*uhrt, wenn die Vorschrift
  2042. angewandt wird.
  2043. .lp
  2044. Zum Zugriff auf den durch das Muster beschriebenen Teil des Baumes
  2045. k\*onnen die Selektoren des Musters verwendet werden, wobei zwei
  2046. F\*alle zu unterscheiden sind. Folgt dem Selektor ein Punkt, wird
  2047. ein Zugriff auf ein Attribut angenommen und der Selektor wird
  2048. automatisch durch den Zugriff auf den entsprechenden Knoten im Baum
  2049. ersetzt. Folgt kein Punkt, wird der Selektor durch einen Zeiger auf den
  2050. Baum ersetzt.
  2051. .lp
  2052. Bei Funktionsaufrufen innerhalb der Vorschrift sollte das erste
  2053. Argument, das den zu transformierenden Baum beschreibt, normalerweise
  2054. eine Selektor sein, da nur dann vom Ge\%ne\%ra\%tor gepr\*uft werden
  2055. kann, ob das
  2056. Argument im Definitionsbereich liegt. Da es jedoch in speziellen F\*allen
  2057. zweckm\*a\*sig ist, einen Baum zu transformieren, der durch ein
  2058. vererbtes Attribut beschrieben wird, wird es auch akzeptiert, wenn der zu
  2059. transformierende Baum auf andere Weise spezifiziert wird.
  2060. .SH 2 "Bedingungen"
  2061. .lp
  2062. Um die Anwendbarkeit einer Vorschrift einzuschr\*anken, kann eine
  2063. \fIBedingung\fP (condition) an die Attribute gestellt werden.
  2064. Eine Bedingung wird durch eine booleschen Ausdruck in Form von
  2065. Quelltext beschrieben.
  2066. .lp
  2067. Selektoren k\*onnen in den Bedingungen ebenfalls verwendet werden.
  2068. .lp
  2069. Der Aufruf von Funktionen und Prozeduren ist in Bedingungen
  2070. prinzipiell m\*oglich,
  2071. die verwendeten Funktionen sollten jedoch keine Seiteneffekte
  2072. haben, da die Reihenfolge, in der die Bedingungen getestet werden
  2073. nicht festgelegt ist. Au\*serdem darf keine Funktion f\*ur die
  2074. Wurzel des Musters aufgerufen werden, da die Vorschrift die hierzu
  2075. ben\*otigt wird, von eben dieser Bedingung abh\*angen k\*onnte.
  2076. .DS
  2077. .TS
  2078. llll.
  2079. condition    \(eq    \fBCONDITION\fP
  2080.           '{' source_text '}'    \fIAusdruck zur Berechnung der Bedingung\fP
  2081. .TE
  2082. .DE 14 "Bedingungen"
  2083. Beispiel:
  2084. .(l I
  2085. .ta 5 10 15 20 25 30 35 40 45
  2086. .sz -2
  2087. \&'*' (expr, const)    \fBCONDITION\fP    { IsPowerOf2 (const.value) }
  2088.         {
  2089.         ...
  2090.         }
  2091. .sz +2
  2092. .)l
  2093. .SH 2 "Kosten"
  2094. .lp
  2095. Um die \fIKosten\fP, die bei Anwendung eine Vorschrift entstehen,
  2096. zu beschreiben, gibt es zwei M\*oglichkeiten.
  2097. Die Kosten werden entweder durch eine Konstante (number) festgelegt
  2098. oder es wird ein Ausdruck (source text) angegeben, die die Kosten
  2099. f\*ur den gesamten durch das Muster abgedeckten Baum berechnen.
  2100. Im ersten Fall werden die Kosten, die durch Funktionsaufrufe innerhalb
  2101. der Vorschriften verursacht werden, automatisch mit einfacher
  2102. Gewichtung ber\*ucksichtigt.
  2103. Im zweiten Fall ist dies Aufgabe des Anwenders.
  2104. .DS
  2105. .TS
  2106. llll.
  2107. costs    \(eq    \fBCOSTS\fP
  2108.           (number    \fIBeschreibung der Kosten durch eine Konstante\fP
  2109.           \(or '{' source_text '}')    \fIAusdruck zur Berechnung der Kosten\fP
  2110. .TE
  2111. .DE 15 "Kosten"
  2112. Um diese Kosten zu ber\*ucksichtigen, stehen dem Anwender Prozeduren zur
  2113. Verf\*ugung, die die Kosten f\*ur eine bestimmte Funktion liefern. Die
  2114. Namen dieser Prozeduren setzen sich aus dem Wort 'Cost' und dem Name
  2115. der betreffenden Funktion zusammen. Als einziges Argument wird der
  2116. Selektor des betreffenden Teilbaums erwartet.
  2117. .lp
  2118. Beispiel:
  2119. .(l I
  2120. .sz -2
  2121. \&'+' (e1: expr, e2:expr)    \fBCOSTS\fP    { 1 + 2 * CostF (e1) + CostF (e2) }
  2122.                     {
  2123.                     ...  F (e1); ...  F (e2); ...
  2124.                     }
  2125. .sz +2
  2126. .)l
  2127. Falls die Kosten nicht explizit angegeben werden, wird \fICOSTS 1\fP
  2128. angenommen.
  2129. .SH 2 "Vereinbarungen"
  2130. .lp
  2131. Die \fIVereinbarungen\fP (declarations) sind lokal d.h. nur f\*ur die
  2132. Anweisungen einer Vorschrift sichtbar.
  2133. Sie k\*onnen z.B. benutzt werden, um Variablen zu vereinbaren, die nur
  2134. in den Anweisungen einer Vorschrift ben\*otigt werden.
  2135. .DS
  2136. .TS
  2137. llll.
  2138. declarations    \(eq    \fBDECLARE\fP '{' source_text '}'
  2139. .TE
  2140. .DE 16 "Vereinbarungen"
  2141. Beispiel:
  2142. .(l I
  2143. .sz -2
  2144. \fBDECLARE\fP    {
  2145. VAR I,J: INTEGER;
  2146. .sz +2
  2147. }
  2148. .)l
  2149. .SH 2 "Integration"
  2150. .lp
  2151. Die optionalen EXPORT-, LOCAL-, BEGIN- und CLOSE-Abschnitte 
  2152. werden verwendet, um das generierte Programm in die Umgebung zu
  2153. integrieren. Der Quelltext im EXPORT-Abschnitt dient zur
  2154. Vereinbarung globaler Daten, die auch au\*serhalb des generierten
  2155. Programms sichtbar sein sollen. Der GLOBAL-Abschnitt enth\*alt von
  2156. au\*sen nicht sichtbare globale Vereinbarungen. Die Anweisungen im
  2157. BEGIN-Abschnitt werden vor der Transformation ausgef\*uhrt, die im
  2158. CLOSE-Abschnitt danach. Der Zweck der beiden letzten Abschnitte
  2159. besteht darin, globale Daten zu initialisieren, bevor eine
  2160. Transformation durchgef\*uhrt wird, sowie Abschlu\*sarbeiten (z.B.
  2161. Speicherbereinigung oder Schlie\*sen von Dateien) durchzuf\*uhren,
  2162. nachdem die Transformation abgeschlossen ist.
  2163. .DS
  2164. .TS
  2165. llll.
  2166.  
  2167. integration    \(eq    [ \fBEXPORT\fP '{' source_text '}' ]    \fI\*offentliche Vereinbarungen\fP
  2168.         [ \fBGLOBAL\fP '{' source_text '}' ]    \fIglobale Vereinbarungen\fP
  2169.         [ \fBBEGIN\fP '{' source_text '}' ]    \fIAnweisungen zur Initialisierung\fP
  2170.         [ \fBCLOSE\fP '{' source_text '}' ]    \fIAnweisungen zum Abschlu\*s\fP
  2171. .TE
  2172. .DE 17 "Integration"
  2173. .BP
  2174. .SH 1 "Implementierung von Transformationen durch ESTRA"
  2175. .lp
  2176. Im folgenden werden die Struktur von mit ESTRA erzeugten Transformatoren
  2177. und deren wesentliche Eigenschaften beschrieben. Es kann jedoch nicht
  2178. Aufgabe diese Kapitels sein, s\*amtliche Details der erzeugten
  2179. Implementierungen zu besprechen. Diese Details kann der interessierte
  2180. Leser im Anhang B.2 finden. Das Beispiel im Anhang ist \*uberdies
  2181. geeignet, die folgenden Ausf\*uhrungen zu erg\*anzen.
  2182. .lp
  2183. Mit ESTRA generierte Transformatoren f\*uhren die Transformation in
  2184. zwei Schritten durch. Im ersten Schritt (Vorbereitung) wird festgelegt, welche
  2185. Vorschriften zur Transformation des speziellen Baumes im einzelnen
  2186. anzuwenden sind. Im zweiten Schritt (Durchf\*uhrung) werden diese
  2187. Vorschriften angewandt.
  2188. .lp
  2189. Zur Vorbereitung der Transformation werden in jedem Knoten des Baumes
  2190. die Vorschriften mit den geringsten Kosten f\*ur die Durchf\*uhrung
  2191. einer Funktion festgehalten. Um diese Vorschriften zu ermitteln, ist es
  2192. notwendig, f\*ur jede Vorschrift zu pr\*ufen, ob das Muster auf den
  2193. Knoten pa\*st und die Bedingung (sofern vorhanden) erf\*ullt ist.
  2194. Dann mu\*s f\*ur jede Funktion von den verbliebenen Vorschriften
  2195. diejenige mit den geringsten Kosten im Knoten festgehalten werden.
  2196. .lp
  2197. Da die Kosten f\*ur die Anwendung einer Vorschrift im allgemeinen
  2198. von den Kosten der S\*ohne (bzw. 'Nachkommen') des Knotens
  2199. abh\*angig sind, mu\*s diese Berechnung in einem Bottom-Up-Durchlauf
  2200. durch den Baum erfolgen.
  2201. .lp
  2202. Die Durchf\*uhrung der Transformation erfolgt durch Anwendung der
  2203. ersten Funktion auf die Wurzel, d.h. die Vorschrift, die in der Wurzel
  2204. f\*ur diese Funktion festgehalten wurde, wird ausgef\*uhrt.
  2205. Funk\%tions\%aufrufe f\*ur Teilb\*aume, die bei der Abarbeitung
  2206. einer Vorschrift anfallen, werden rekursiv abgearbeitet.
  2207. .SH 2 "Vorbereitung der Transformation"
  2208. .lp
  2209. Bevor die Transformation in der obengenannten Weise durchgef\*uhrt
  2210. werden kann, mu\*s sie durch die Festlegung der L\*osung mit
  2211. minimalen Kosten vorbereitet werden.
  2212. .lp
  2213. Die Vorbereitung entspricht einer S-Attributierung, bei der f\*ur jeden
  2214. Knoten die folgenden Attribute berechnet werden:
  2215. .np
  2216. die Menge der Klassen, zu denen der Knoten geh\*ort
  2217. .np
  2218. die Vorschriften, die auf den Knoten (genauer dessen Teilbaum)
  2219. anwendbar sind
  2220. .np
  2221. f\*ur jede Funktion die Vorschrift, die diese mit den geringsten
  2222. Kosten realisiert und die hierbei entstehenden Kosten
  2223. .lp
  2224. Die rekursive Prozedur yyTraverse, die diese Attribute berechnet, hat
  2225. folgenden Aufbau:
  2226. .np
  2227. Beschaffung von Speicher f\*ur die Attribute
  2228. .np
  2229. Prozeduraufrufe zur Berechnung der Attribute der S\*ohne
  2230. des Knotens
  2231. .np
  2232. Berechnung der Klassen des aktuellen Teilbaums
  2233. .np
  2234. Berechnung der zul\*assigen Vorschriften
  2235. .np
  2236. Berechnung der kosteng\*unstigsten Vorschrift f\*ur die einzelnen
  2237. Funktionen
  2238. .SH 2 "Darstellung von Funktionen und Vorschriften"
  2239. .lp
  2240. In Modula-2\*([<\*([[Wir85\*(]]\*(>] werden sowohl die Funktionen als auch die Vorschriften
  2241. (genauer die Vereinbarungen und Anweisungen der Vorschriften) als
  2242. Prozeduren realisiert. Die Prozeduren, die den Funktionen entsprechen,
  2243. w\*ahlen hierbei lediglich die Vorschrift aus und rufen die
  2244. entsprechende Prozedur auf. Das bedeutet, da\*s bei der
  2245. Durchf\*uhrung einer Transformation f\*ur jede Anwendung einer
  2246. Vorschrift zwei Prozeduraufrufe notwendig sind. Besser w\*are es,
  2247. wenn man mit je einem Aufruf ausk\*ame.
  2248. .lp
  2249. Um dies zu erreichen gibt es zwei M\*oglichkeiten. Entweder man spart
  2250. die Prozeduren der Funktionen, d.h. die Auswahl der Vorschrift wird an
  2251. den Ort des Funk\%tions\%aufrufs verschoben, oder man spart die Prozeduren
  2252. f\*ur die Vorschriften, d.h. alle Vorschriften einer Funktion werden
  2253. in die Prozedur der Funktion eingebettet.
  2254. .lp
  2255. Die Information, welche Vorschriften im einzelnen anzuwenden sind,
  2256. wird nicht unmittelbar in den Knoten gespeichert. Es ist vielmehr so,
  2257. da\*s dort lediglich eine Adresse zu finden ist, die einen Verweis
  2258. auf diese Information darstellt (vgl. Kapitel 9).
  2259. Infolgedessen ist vor dem Zugriff auf diese Information eine
  2260. Typwandlung, die die Adresse in den erforderlichen Zeigertyp wandelt,
  2261. notwendig.
  2262. .lp
  2263. Um aber in Modula-2 eine Adresse in einen Zeiger umzuwandeln und auf
  2264. die zugeh\*orige Information \*uber diesen Zeiger zuzugreifen, ist eine
  2265. Zuweisung erforderlich. Dies bedeutet, da\*s beim Verschieben der
  2266. Auswahl an den Ort des Funk\%tions\%aufrufs f\*ur jeden Aufruf eine
  2267. zus\*atzliche Anweisung, eben diese Zuweisung, erforderlich ist. Da der
  2268. Aufwand, diese Anweisung in die vom Anwender vorgegebenen Anweisungen
  2269. einzuf\*ugen, recht gro\*s w\*are, wurde diese M\*oglichkeit
  2270. verworfen.
  2271. .lp
  2272. Die zweite M\*oglichkeit, die darin besteht, alle Vorschriften einer
  2273. Funktion in eine Prozedur zu packen, scheitert in Modula-2 daran, da\*s die
  2274. lokalen Vereinbarungen, die zu den einzelnen Vorschriften geh\*oren,
  2275. in der Regel nicht in einer Prozedur untergebracht werden k\*onnen, da es
  2276. sonst zu Namenskonflikten zwischen diesen Vereinbarungen kommt.
  2277. .lp
  2278. In der Programmiersprache C\*([<\*([[KeR83\*(]]\*(>] sind hingegen
  2279. beide L\*osung realisierbar, da weder die Typwandlung (type cast)
  2280. noch die Vereinbarung von lokalen Daten (innerhalb von Bl\*ocken)
  2281. Probleme darstellen. Da bei der zweiten L\*osung insgesamt weniger
  2282. Funktionen (die Unterprogramme in C werden als Funktionen bezeichnet)
  2283. ben\*otigt werden und bei dieser L\*osung au\*serdem weniger
  2284. Aufwand beim Umsetzen der Anweisungen der einzelnen Vorschriften
  2285. erforderlich ist, ist diese bei der Verwendung von C vorzuziehen.
  2286. .SH 2 "Darstellung der Attribute"
  2287. .lp
  2288. Die Klassen des aktuellen Teilbaums werden als Menge dargestellt und
  2289. in Modula-2 als ARRAY OF BITSET realisiert. Zur Darstellung der
  2290. einzelnen Klassen werden diese durch\%numeriert.
  2291. Die zul\*assigen Vorschriften werden durch ein boolesches Feld
  2292. realisiert.
  2293. Die kosteng\*unstigste Vorschrift jeder Funktion wird durch den Wert
  2294. einer Prozedur-Variablen und die zugeh\*origen Kosten durch einen INTEGER-Wert
  2295. dargestellt.
  2296. .lp
  2297. Mit Ausnahme der zul\*assigen Vorschriften werden alle Attribute im
  2298. Knoten abgespeichert. Bei den zul\*assigen Vorschriften ist dies
  2299. nicht notwendig, da diese nur solange ben\*otigt werden, bis die
  2300. kosteng\*unstigsten Vorschriften feststehen. Lokale Variablen der
  2301. Prozedur yyTraverse w\*urden deshalb zu Realisierung vollkommen
  2302. ausreichen.
  2303. .lp
  2304. Da aber au\*serdem der Zeitraum von Berechnung bis Auswertung
  2305. der zul\*assigen Vorschriften f\*ur verschiedene Knoten v\*ollig
  2306. disjunkt ist, gen\*ugt sogar ein einziges globales Feld zur Darstellung.
  2307. .SH 2 "Speicherverwaltung"
  2308. .lp
  2309. Da Gr\*o\*se und Struktur der Daten, die zur Vorbereitung der
  2310. Transformation ben\*otigt werden, bei der Implementierung des Baumes
  2311. i.a. nicht bekannt sind, wird im Baum lediglich Platz f\*ur eine
  2312. Adresse reserviert. Bei der Vorbereitung der Transformation wird dann
  2313. f\*ur jeden Knoten dynamischer Speicher beschafft, um die Attribute
  2314. abzuspeichern. Der Zeiger auf den dynamischen Speicher wird im Knoten
  2315. abgelegt, soda\*s \*uber die Knoten jederzeit auf die Attribute
  2316. zugegriffen werden kann.
  2317. .lp
  2318. Da diese Attribute nach Durchf\*uhrung der Transformation nicht mehr
  2319. ben\*otigt werden, sollte der belegte Speicher wieder freigegeben
  2320. werden. Um dies effizient durchzuf\*uhren, enth\*alt der generierte
  2321. Transformator eine eigene Speicherverwaltung, die nach dem
  2322. Haldenprinzip arbeitet. Die Speicherverwaltung beschafft den
  2323. Speicher in gr\*o\*seren Einheiten vom System und vergibt ihn im
  2324. ben\*otigten Umfang. Nach der Transformation wird der Speicher
  2325. schlie\*slich in den gro\*sen Einheiten, die bereits bei der
  2326. Beschaffung linear verkettet wurden, wieder freigegeben.
  2327. .lp
  2328. Durch diese Methode wird zweierlei erreicht. Zum einen kann die
  2329. Speicherfreigabe sehr schnell durchgef\*uhrt werden, da kein
  2330. aufwendiger Durchlauf durch den Baum notwendig ist, wie er
  2331. entst\*unde, wenn der vergebene Speicher nur \*uber
  2332. die Knoten zu erreichen w\*are. Au\*serdem wird vermieden, da\*s
  2333. der Speicher durch die Verwendung in kleine, kaum wiederverwendbare
  2334. St\*ucke zerf\*allt.
  2335. .SH 2 "Berechnung der Klassen"
  2336. .lp
  2337. Grundlage zur Berechnung der Klassen des aktuellen Teilbaums sind die
  2338. Knotenbeschreibungen. Da die Berechnung abh\*angig vom aktuellen
  2339. Knoten durchgef\*uhrt wird, gen\*ugt es hierbei, die
  2340. Knotenbeschreibungen zu betrachten, die zum aktuellen Knoten passen.
  2341. .lp
  2342. Falls alle S\*ohne eines Knotens zu den jeweiligen Klassen aus
  2343. der Knotenbeschreibung passen, pa\*st auch der
  2344. aktuelle Teilbaum zu dieser Knotenbeschreibung. Folglich pa\*st
  2345. auch die Klasse auf der linken Seite der zugeh\*origen
  2346. Knotenproduktion.
  2347. .lp
  2348. Da mit einer Klasse immer auch deren Oberklasse auf einen Teilbaum
  2349. pa\*st, wird hier nicht nur diese Klasse, sondern auch deren transitive
  2350. H\*ulle bez\*uglich der Oberklassenrelation erkannt.
  2351. .lp
  2352. Da die Hauptbeschreibung eines Knotens immer auf diesen Knoten
  2353. passen mu\*s, wird deren transitive H\*ulle immer in die Klassen
  2354. des aktuellen Teilbaumes aufgenommen. Beim Erkennen einer
  2355. Knotenbeschreibung k\*onnen diese deshalb vernachl\*assigt werden,
  2356. da sie ja ohnehin erkannt werden.
  2357. .SH 2 "Berechnung der zul\*assigen Vorschriften"
  2358. .lp
  2359. Um die zul\*assigen Vorschriften festzulegen, werden die Muster der
  2360. Vorschriften, mit dem Teilbaum verglichen. Zu diesem Zweck werden alle
  2361. Muster betrachtet, die mit dem aktuellen Knoten vertr\*aglich sind.
  2362. Es werden als nur solche Muster untersucht, die mit dem aktuellen
  2363. Knoten beginnen, oder einer Klasse darstellen, aus der der aktuelle
  2364. Knoten ableitbar ist.
  2365. .lp
  2366. Um festzustellen, ob ein Muster mit dem
  2367. aktuellen Teilbaum \*ubereinstimmt, wird jeder Knoten und jede Klasse
  2368. des Muster mit dem aktuellen Teilbaum verglichen. Falls es sich bei
  2369. der Wurzel eines Musters um einen Knoten handelt, mu\*s dieser nicht
  2370. \*uberpr\*uft werden, da seine \*Ubereinstimmung bereits durch die
  2371. Auswahl der Muster gegeben ist. Ebenso ist es nicht erforderlich,
  2372. Klassen im Muster zu \*uberpr\*ufen, die bei einer Normierung des Musters
  2373. entfallen, da diese immer vorliegen, wenn der Baum der gegebenen
  2374. Grammatik gen\*ugt.
  2375. .lp
  2376. Bei \*Ubereinstimmung des Musters mit dem
  2377. Teilbaum und Zutreffen der eventuell vorhandenen Bedingung wird
  2378. die Vorschrift festgehalten.
  2379. .SH 2 "Berechnung der kosteng\*unstigsten Vorschriften"
  2380. .lp
  2381. Zur Festlegung der kosteng\*unstigsten Vorschrift werden die Kosten
  2382. aller anwendbaren Vorschriften bestimmt. Ergeben sich dabei
  2383. f\*ur eine Funktion geringere Kosten als sie zuvor vorlagen, werden die
  2384. betreffende Funktion und diese Kosten festgehalten. Da die Kosten
  2385. einer Vorschrift von den Kosten einer Funktion f\*ur den selben
  2386. Knoten abh\*angen k\*onnen, gen\*ugt es i.a. jedoch nicht,
  2387. f\*ur jede Vorschrift einmal die Kosten zu berechnen. Die einfachste
  2388. Vorgehensweise besteht darin, die Berechnung der Kosten f\*ur
  2389. alle Vorschriften solange zu wiederholen, bis sich keine Verbesserungen
  2390. der Kosten mehr ergeben. Da dieses Verfahren zu sehr vielen unn\*otigen
  2391. Berechnungen f\*uhren mu\*s, wird eine Optimierung durchgef\*uhrt,
  2392. die in den meisten praktischen F\*allen mit einem Durchlauf auskommt.
  2393. .lp
  2394. Offensichtlich ist eine Wiederholung der Berechnung, wenn \*uberhaupt
  2395. dann nur f\*ur solche Vorschriften erforderlich, deren Kosten von den
  2396. Kosten einer anderen Funktion f\*ur den aktuellen Knoten abh\*angen.
  2397. Die Vorschriften werden deshalb gem\*a\*s diesem Kriterium in zwei
  2398. Gruppen gegliedert. Die
  2399. eine Gruppe (und die umfa\*st in der Praxis alle oder zumindest die
  2400. meisten Vorschriften) mu\*s nur einmal abgearbeitet werden. Die
  2401. \*ubrigen Vorschriften werden (sofern mindestens zwei verbleiben)
  2402. wiederholt abgearbeitet, bis sich bei einem Durch\%lauf keine
  2403. Verbesserung ergibt.
  2404. .BP
  2405. .SH 1 "Bottom-Up Pattern-Matching mit einem Baumautomaten"
  2406. .lp
  2407. Bei dem in Kapitel 6 vorgestellten Verfahren zum Festlegen der
  2408. auf einen Teilbaum anwendbaren Vorschriften wird
  2409. jedes Muster getrennt betrachtet. Das
  2410. hat zur Folge, da\*s der Aufwand f\*ur diesen Schritt mit Zahl
  2411. und Gr\*o\*se der zu untersuchenden Muster zunimmt.
  2412. Beim sogenannten Bottom-Up Pattern-Matching mit einem Baumautomaten
  2413. \*([[HoO82\*(]] wird dies vermieden.
  2414. .lp
  2415. Bei diesem Verfahren werden zum Zeitpunkt der Generierung alle Mengen
  2416. von Mustern be\%stimmt, die f\*ur das Pattern-Matching von Bedeutung sind.
  2417. Diese Mengen bilden den Zu\%stands\%raum des Baumautomaten. Das Pattern-Matching
  2418. erfolgt dann, indem f\*ur jeden Knoten des Baumes der Zustand berechnet wird,
  2419. der die Menge von Mustern darstellt, welche auf den zugeh\*origen
  2420. Teilbaum passen.
  2421. Aus diesem Zustand l\*a\*st sich unmittelbar ablesen, welche
  2422. Vorschriften aufgrund ihrer Muster in Frage kommen.
  2423. Eventuell vorhandene Bedingungen m\*ussen weiterhin 
  2424. gesondert \*uberpr\*uft werden.
  2425. .SH 2 "Relevante Muster"
  2426. .lp
  2427. Bevor der Zustandsraum bestimmt werden kann, m\*ussen die relevanten
  2428. Muster, d.h. die Muster, die f\*ur das Bottom-Up Pattern-Matching
  2429. von Bedeutung sind, festgelegt werden. Grundlage f\*ur die
  2430. Bestimmung der relevanten Muster sind die normierten Muster der
  2431. gegebenen Vorschriften.
  2432. .lp
  2433. F\*ur eine gegebene Menge P\*<N\*> normierter Muster ist die Menge
  2434. relevanter Muster die kleinste Menge P\*<R\*> mit den Eigenschaften:
  2435. .np
  2436. P\*<N\*> \(ib P\*<R\*>
  2437. .br
  2438. Die vorgegeben normierten Muster sind relevant.
  2439. .np
  2440. n (p\*<1\*>, ..., p\*<m\*>) \(mo P\*<R\*>
  2441. \(RA p\*<1\*> \(mo  P\*<R\*>, ..., p\*<m\*> \(mo  P\*<R\*>
  2442. .br
  2443. Wenn ein Muster relevant ist, sind auch alle seine
  2444. Teilmuster relevant.
  2445. .np
  2446. c \(mo P\*<R\*>, c \(-> n (p\*<1\*>, ..., p\*<m\*>)
  2447. \(RA Normalize (n (p\*<1\*>, ..., p\*<m\*>)) \(mo P\*<R\*>
  2448. .br
  2449. Ist ein einer Klasse entsprechendes Muster relevant, dann ist auch jedes
  2450. normierte Muster einer aus dieser Klasse ableitbaren Knotenbeschreibung
  2451. relevant.
  2452. .lp
  2453. Durch (1) wird sichergestellt, da\*s die vorgegebenen Muster, die beim
  2454. Pattern-Matching erkannt werden sollen, in der Menge P\*<R\*> enthalten
  2455. sind. Mit (2) wird daf\*ur gesorgt, da\*s auch die Teilmuster,
  2456. die zum Erkennen eines Musters beitragen, in P\*<R\*> enthalten sind.
  2457. Da die Klassen zwar in den Mustern, nicht aber im realen Baum
  2458. vorkommen, m\*ussen die normierten Muster aller Knotenbeschreibungen,
  2459. die einer in P\*<R\*> enthaltenen Klasse entsprechen, ebenfalls in
  2460. P\*<R\*> liegen (3), damit die Klassen anhand dieser Muster erkannt
  2461. werden k\*onnen.
  2462. .lp
  2463. Abb. \n($1.1 zeigt die relevanten Muster, die entstehen, wenn
  2464. wir die Mustern '+' (const, const) und '+' (expr, expr) zugrunde
  2465. legen.
  2466. .DS 
  2467. .ta 1.5c 3c 6c
  2468. P\*<N\*> = { p\*<0\*>, p\*<1\*> }
  2469. P\*<R\*> = { p\*<0\*>, p\*<1\*>, p\*<2\*>, p\*<3\*> }
  2470.  
  2471. mit:
  2472. p\*<0\*> =    '+'    (const, const)
  2473. p\*<1\*> =    '+'    (:, :)    \fINormierung von '+' (expr, expr)\fP
  2474. p\*<2\*> =    const        \fITeilmuster von p\*<0\*>\fP
  2475. p\*<3\*> =    Const    ()    \fIBeschreibung eines Knotens der Klasse const\fP
  2476. .DE 1 "relevante Muster"
  2477. .SH 2 "Zust\*ande"
  2478. .lp
  2479. Zur Beschreibung der Zust\*ande Q des Baumautomaten k\*onnte die
  2480. Menge 2\u\s-2P\d\s-2R\s+2\u\s+2\d verwendet werden.
  2481. Tats\*achlich k\*onnen jedoch nicht alle Teilmengen von P\*<R\*> als
  2482. Zust\*ande vorkommen, da alle Zust\*ande notwendigerweise die folgenden
  2483. Bedingungen erf\*ullen m\*ussen.
  2484. .np
  2485. p\*<1\*>, p\*<2\*> \(mo q \(RA \(no p\*<1\*>\(or\(orp\*<2\*>
  2486. .np
  2487. p\*<1\*> \(mo P\*<R\*>, p\*<2\*> \(mo q, p\*<1\*><p\*<2\*>
  2488. \(RA p\*<1\*> \(mo q
  2489. .lp
  2490. Die Bedingungen resultieren daraus, das jeder Zustand einen realen
  2491. Baum beschreiben mu\*s. Es ist deshalb nicht m\*oglich, da\*s ein
  2492. Zustand zwei sich widersprechende Muster enth\*alt (1). Au\*serdem
  2493. mu\*s mit dem gr\*o\*seren Muster p\*<2\*> immer auch das kleinere
  2494. Muster p\*<1\*> in q liegen.
  2495. .lp
  2496. In unserem Beispiel erf\*ullen nur sechs der 16 Mengen diese
  2497. Eigenschaften (Abb. \n($1.2). Die \*ubrigen scheiden aus (Abb. \n($1.3).
  2498. .DS
  2499. Q = { q\*<0\*>, q\*<1\*>, q\*<2\*>, q\*<3\*>, q\*<4\*>, q\*<5\*> }
  2500.  
  2501. mit:
  2502. q\*<0\*> =    { p\*<0\*>, p\*<1\*>, p\*<2\*> }
  2503. q\*<1\*> =    { p\*<1\*>, p\*<2\*> } 
  2504. q\*<2\*> =    { p\*<1\*> } 
  2505. q\*<3\*> =    { p\*<2\*>, p\*<3\*> }
  2506. q\*<4\*> =    { p\*<2\*> }
  2507. q\*<5\*> =    { } 
  2508. .DE 2 "Zust\*ande des Baumautomaten"
  2509. Da\*s die angegebenen Bedingungen nicht hinreichend sind,
  2510. zeigt sich an unserem Beispiel. Auf Grund der Grammatik (Abb. 7.1.) mu\*s
  2511. immer, wenn die Muster p\*<1\*> und p\*<2\*> passen, auch p\*<0\*> passen. Damit
  2512. scheidet der Zustand q\*<1\*>, der nur aus p\*<1\*> und p\*<2\*> besteht, aus. Der Zustand
  2513. q\*<4\*> kann ebenfalls nie auftreten, da p\*<2\*> nur passen kann, wenn
  2514. auch p\*<1\*> oder p\*<3\*> pa\*st.
  2515. .DS
  2516. .ta 4c
  2517. { p\*<0\*>, p\*<1\*>, p\*<2\*>, p\*<3\*> }    nicht relevant da: p\*<0\*> \(or\(or p\*<3\*>
  2518. { p\*<0\*>, p\*<1\*>, p\*<3\*> }    nicht relevant da: p\*<0\*> \(or\(or p\*<3\*>
  2519. { p\*<0\*>, p\*<1\*> }    nicht relevant da: p\*<2\*> < p\*<0\*>
  2520. { p\*<0\*>, p\*<2\*>, p\*<3\*> }    nicht relevant da: p\*<0\*> \(or\(or p\*<3\*>
  2521. { p\*<0\*>, p\*<2\*> }    nicht relevant da: p\*<1\*> < p\*<0\*>
  2522. { p\*<0\*>, p\*<3\*> }    nicht relevant da: p\*<2\*> < p\*<0\*>
  2523. { p\*<0\*> }    nicht relevant da: p\*<1\*> < p\*<0\*>
  2524. { p\*<1\*>, p\*<2\*>, p\*<3\*> }    nicht relevant da: p\*<1\*> \(or\(or p\*<3\*>
  2525. { p\*<1\*>, p\*<3\*> }    nicht relevant da: p\*<1\*> \(or\(or p\*<3\*>
  2526. { p\*<3\*> }    nicht relevant da: p\*<1\*> < p\*<3\*>
  2527. .DE 3 "nicht relevante Mengen von Mustern"
  2528. Ein Ansatz zur Beseitigung dieses Mangel wird in Kapitel \n($1.7
  2529. gegeben.
  2530. .lp
  2531. In der Hauptbeschreibung eines Knotens ist f\*ur jeden Sohn eine
  2532. Klasse festgelegt. F\*ur jeden Sohn sind deshalb nur die Zust\*ande
  2533. relevant, die ausschlie\*slich Muster enthalten, die aus dieser Klasse
  2534. abgeleitet werden k\*onnen.
  2535. .lp
  2536. Jeder Klasse c wird deshalb die Menge der f\*ur diese Klasse
  2537. relevanten Muster P\*<c\*> und der f\*ur diese Klasse relevante
  2538. Zust\*ande Q\*<c\*> zugeordnet.
  2539. .ip
  2540. P\*<c\*> := { p \(mo P\*<R\*> \(|? p < c \(bo p = c }
  2541. .br
  2542. Q\*<c\*> := { q \(mo Q \(|? q \(ib P\*<c\*> }
  2543. .lp
  2544. Ebenso wie den Klassen kann man auch jedem Knoten n die Menge der f\*ur
  2545. diesen Knoten relevanten Muster P\*<n\*> und die f\*ur diesen Knoten
  2546. relevanten Zust\*ande Q\*<n\*> zuordnen.
  2547. .ip
  2548. P\*<n\*> := { p \(mo P\*<R\*> \(|? p < n \(bo p = n }
  2549. .br
  2550. Q\*<n\*> := { q \(mo Q \(|? q \(ib P\*<n\*> }
  2551. .SH 2 "Zustands\*ubergangsfunktionen"
  2552. .lp
  2553. Um das Bottom-Up Pattern-Matching durchzuf\*uhren, wird f\*ur jeden
  2554. Knoten n eine Zustands\*ubergangsfunktion f\*<n\*> ben\*otigt.
  2555. Die Stelligkeit von f\*<n\*> entspricht der Wertigkeit m des Knotens n.
  2556. .ip
  2557. f\*<n\*>: Q\d\s-2\&c\d\s-2\&1\s+2\u\s+2\u \(mu ... \(mu
  2558. Q\d\s-2\&c\d\s-2\&m\s+2\u\s+2\u \(mt Q\*<n\*> 
  2559. .lp
  2560. Die Funktion f\*<n\*> bestimmt aufgrund der Zust\*ande q\*<1\*>, ...,
  2561. q\*<m\*> der S\*ohne eines Knotens n den Zustand f\*ur diesen Knoten.
  2562. .lp
  2563. Um f\*ur gegebene Zust\*ande q\*<1\*>, ..., q\*<m\*>, q = f\*<n\*> (q\*<1\*>,
  2564. \&..., q\*<m\*>) festzulegen, wird so vorgegangen, da\*s f\*ur alle
  2565. Muster p \(mo P\*<n\*> gepr\*uft wird, ob sie in q enthalten sein m\*ussen. 
  2566. .np
  2567. n (p\*<1\*>, ..., p\*<m\*>) \(mo P\*<n\*>,
  2568. p\*<1\*> \(mo q\*<1\*>, ..., p\*<m\*> \(mo q\*<m\*>
  2569. \(RA n (p\*<1\*>, ..., p\*<m\*>) \(mo q
  2570. .np
  2571. c \(-> n (c\*<1\*>, ..., c\*<m\*>),
  2572. Normalize (n (c\*<1\*>, ..., c\*<m\*>)) \(mo q \(RA c \(mo q
  2573. .np
  2574. c \(-> n (c\*<1\*>, ..., c\*<m\*>),
  2575. Normalize (n (c\*<1\*>, ..., c\*<m\*>)) \(eq c \(RA
  2576. c \(mo q
  2577. .lp
  2578. Ein Muster das mit einem Knoten beginnt liegt in q, wenn alle
  2579. Teilmuster p\*<i\*> bereits im entsprechenden Zustand q\*<i\*> liegen (1).
  2580. Das Muster einer Klasse liegt in q falls, eine Knotenbeschreibung dieser Klasse in
  2581. normierter Form bereits in q enthalten ist (2), oder diese normierte
  2582. Form mit der Klasse \*ubereinstimmt (3).
  2583. .lp
  2584. F\*ur unser Beispiel ergeben sich damit folgenden \*Ubergangsfunktionen.
  2585. .DS
  2586. .TS
  2587. lll.
  2588. f\*<'+'\*> (q\*<0\*>, q\*<0\*>) = q\*<0\*>    f\*<'+'\*> (q\*<0\*>, q\*<1\*>) = q\*<0\*>    f\*<'+'\*> (q\*<0\*>, q\*<2\*>) = q\*<2\*>
  2589. f\*<'+'\*> (q\*<0\*>, q\*<3\*>) = q\*<0\*>    f\*<'+'\*> (q\*<0\*>, q\*<4\*>) = q\*<0\*>    f\*<'+'\*> (q\*<0\*>, q\*<5\*>) = q\*<2\*>
  2590. f\*<'+'\*> (q\*<1\*>, q\*<0\*>) = q\*<0\*>    f\*<'+'\*> (q\*<1\*>, q\*<1\*>) = q\*<0\*>    f\*<'+'\*> (q\*<1\*>, q\*<2\*>) = q\*<2\*>
  2591. f\*<'+'\*> (q\*<1\*>, q\*<3\*>) = q\*<0\*>    f\*<'+'\*> (q\*<1\*>, q\*<4\*>) = q\*<0\*>    f\*<'+'\*> (q\*<1\*>, q\*<5\*>) = q\*<2\*>
  2592. f\*<'+'\*> (q\*<2\*>, q\*<0\*>) = q\*<2\*>    f\*<'+'\*> (q\*<2\*>, q\*<1\*>) = q\*<2\*>    f\*<'+'\*> (q\*<2\*>, q\*<2\*>) = q\*<2\*>
  2593. f\*<'+'\*> (q\*<2\*>, q\*<3\*>) = q\*<2\*>    f\*<'+'\*> (q\*<2\*>, q\*<4\*>) = q\*<2\*>    f\*<'+'\*> (q\*<2\*>, q\*<5\*>) = q\*<2\*>
  2594. f\*<'+'\*> (q\*<3\*>, q\*<0\*>) = q\*<0\*>    f\*<'+'\*> (q\*<3\*>, q\*<1\*>) = q\*<0\*>    f\*<'+'\*> (q\*<3\*>, q\*<2\*>) = q\*<2\*>
  2595. f\*<'+'\*> (q\*<3\*>, q\*<3\*>) = q\*<0\*>    f\*<'+'\*> (q\*<3\*>, q\*<4\*>) = q\*<0\*>    f\*<'+'\*> (q\*<3\*>, q\*<5\*>) = q\*<2\*>
  2596. f\*<'+'\*> (q\*<4\*>, q\*<0\*>) = q\*<0\*>    f\*<'+'\*> (q\*<4\*>, q\*<1\*>) = q\*<0\*>    f\*<'+'\*> (q\*<4\*>, q\*<2\*>) = q\*<2\*>
  2597. f\*<'+'\*> (q\*<4\*>, q\*<3\*>) = q\*<0\*>    f\*<'+'\*> (q\*<4\*>, q\*<4\*>) = q\*<0\*>    f\*<'+'\*> (q\*<4\*>, q\*<5\*>) = q\*<2\*>
  2598. f\*<'+'\*> (q\*<5\*>, q\*<0\*>) = q\*<2\*>    f\*<'+'\*> (q\*<5\*>, q\*<1\*>) = q\*<2\*>    f\*<'+'\*> (q\*<5\*>, q\*<2\*>) = q\*<2\*>
  2599. f\*<'+'\*> (q\*<5\*>, q\*<3\*>) = q\*<2\*>    f\*<'+'\*> (q\*<5\*>, q\*<4\*>) = q\*<2\*>    f\*<'+'\*> (q\*<5\*>, q\*<5\*>) = q\*<2\*>
  2600. .TE
  2601. f\*<Const\*> () = q\*<3\*>
  2602. f\*<Ident\*> () = q\*<5\*>
  2603. .DE 4 "Zustands\*ubergangsfunktionen"
  2604. .lp
  2605. Das Pattern-Matching l\*auft nun so ab, da\*s in einem
  2606. Bottom-Up-Durchlauf durch den Baum f\*ur jeden Knoten ein Zustand
  2607. q\(moQ berechnet wird. Diese Berechnung erfolgt, indem die zum jeweiligen
  2608. Knoten n geh\*orige Funktion f\*<n\*> auf die bereits berechneten
  2609. Zust\*ande q\*<1\*>, ..., q\*<m\*> der S\*ohne angewandt wird.
  2610. .SH 2 "Felder zur Darstellung der Zustands\*ubergangsfunktionen"
  2611. .lp
  2612. Um die Zustands\*ubergangsfunktionen darzustellen, k\*onnte man
  2613. f\*ur jeden Knoten ein Feld vorsehen. Die Felder h\*atten
  2614. jeweils soviele Dimensionen, wie der zugeh\*orige Knoten S\*ohne
  2615. hat. Die Eintr\*age der Felder k\*onnen zum Zeitpunkt der Generierung
  2616. bestimmt werden.  Zur Laufzeit w\*are lediglich ein Zugriff auf das Feld
  2617. erforderlich, um den Zustand f\*ur den aktuellen Knoten zu bestimmen.
  2618. .DS
  2619. \&'+'    (i, j)
  2620. .TS
  2621. box;
  2622. r|rrrrrr.
  2623. i \e j    q\*<0\*>    q\*<1\*>    q\*<2\*>    q\*<3\*>    q\*<4\*>    q\*<5\*>
  2624. _
  2625. q\*<0\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2626. q\*<1\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2627. q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>
  2628. q\*<3\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2629. q\*<4\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2630. q\*<5\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>
  2631. .TE
  2632.  
  2633. Const    ()
  2634. .TS
  2635. box;
  2636. r.
  2637. q\*<3\*>
  2638. .TE
  2639.  
  2640. Ident    ()
  2641. .TS
  2642. box;
  2643. r.
  2644. q\*<5\*>
  2645. .TE
  2646. .DE 5 "Felder zur Darstellung der Zustands\*ubergangsfunktionen"
  2647. Abb. \n($1.5 zeigt die Felder zur Darstellung der
  2648. Zustands\*ubergangsfunktionen, die sich f\*ur unser Beispiel
  2649. ergeben.
  2650. .lp
  2651. Da f\*ur S\*ohne aus der Klasse c nur Zust\*ande aus
  2652. Q\*<c\*> vorkommen k\*onnen, w\*urde es ausreichen die Felder f\*ur
  2653. diesen Teil zu realisieren. Da aber Muster und damit auch Zust\*ande
  2654. durchaus f\*ur verschiedene Klassen relevant sein k\*onnen, kann die
  2655. Codierung dieser Zust\*ande nicht immer dicht liegen. 
  2656. Bei realistischen Beispielen w\*aren die Felder deshalb sehr
  2657. gro\*s jedoch nicht vollst\*andig besetzt.
  2658. .lp
  2659. Um den enormen Speicherbedarf f\*ur die mehrdimensionalen Felder
  2660. zu vermeiden, liegt es nahe, eine Komprimierung durchzuf\*uhren.
  2661. .SH 2 "Automaten zur Darstellung der \*Ubergangsfunktionen"
  2662. .lp
  2663. Die Komprimierung erfolgt in Anlehnung an das in\*([<\*([[BMW87\*(]]\*(>]
  2664. vorgestellte Verfahren.
  2665. Im ersten Schritt werden an Stelle der Felder Automaten aufgebaut.
  2666. Diese Automaten arbeiten horizontal, die S\*ohne eines Knotens werden
  2667. hierbei von links nach rechts abgearbeitet, wobei jeweils
  2668. ein durch den Zustand des Sohnes gesteuerter \*Ubergang im
  2669. Automat stattfindet. Anstelle des Zugriffs auf ein
  2670. n-dimensionales Feld erfolgen also n \*Uberg\*ange in einem
  2671. Automaten.
  2672. .DS
  2673. .PS
  2674. circlerad = 0.15i
  2675. boxht = 0.3i
  2676. boxwid = 0.3i
  2677. define r X (1.6i, 0i) X
  2678. define u X (0i, 1.2i) X
  2679. define d X (0i, -1.2i) X
  2680. define ru X (1.6i, 0.3i) X
  2681. define rd X (1.6i, -0.3i) X
  2682. A:    circle invis
  2683. B:    circle invis at A + d
  2684. C:    circle invis at B + d
  2685. S6:    circle "S1" at A + r
  2686. S3:    box "q\d\s-2\&3\s+2\u" at B + r
  2687. S5:    box "q\d\s-2\&5\s+2\u" at C + r
  2688. arrow "'+'" "" from A to S6 chop
  2689. arrow "Const" "" from B to S3 chop
  2690. arrow "Ident" "" from C to S5 chop
  2691. S7:    circle "S2" at S6 + r + u + u
  2692. S8:    circle "S3" at S6 + r + u
  2693. S9:    circle "S4" at S6 + r
  2694. S10:    circle "S5" at S6 + r + d
  2695. S11:    circle "S6" at S6 + r + d + d
  2696. S12:    circle "S7" at S6 + r + d + d + d
  2697. arrow "q\d\s-2\&0\s+2\u    " "" from S6 to S7 chop
  2698. arrow "q\d\s-2\&1\s+2\u   " "" from S6 to S8 chop
  2699. arrow "q\d\s-2\&2\s+2\u  " "" from S6 to S9 chop
  2700. arrow "  q\d\s-2\&3\s+2\u" "" from S6 to S10 chop
  2701. arrow "   q\d\s-2\&4\s+2\u" "" from S6 to S11 chop
  2702. arrow "    q\d\s-2\&5\s+2\u" "" from S6 to S12 chop
  2703. S7a:    box "q\d\s-2\&0\s+2\u" at S7 + ru
  2704. S7b:    box "q\d\s-2\&2\s+2\u" at S7 + rd
  2705. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,     " "    q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" from S7 to S7a chop
  2706. arrow "" "q\d\s-2\&2\s+2\u,q\d\s-2\&5\s+2\u  " from S7 to S7b chop
  2707. S8a:    box "q\d\s-2\&0\s+2\u" at S8 + ru
  2708. S8b:    box "q\d\s-2\&2\s+2\u" at S8 + rd
  2709. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,     " "    q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" from S8 to S8a chop
  2710. arrow "" "q\d\s-2\&2\s+2\u,q\d\s-2\&5\s+2\u  " from S8 to S8b chop
  2711. S9a:    box "q\d\s-2\&2\s+2\u" at S9 + r
  2712. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,q\d\s-2\&2\s+2\u," "q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u,q\d\s-2\&5\s+2\u" from S9 to S9a chop
  2713. S10a:    box "q\d\s-2\&0\s+2\u" at S10 + ru
  2714. S10b:    box "q\d\s-2\&2\s+2\u" at S10 + rd
  2715. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,     " "    q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" from S10 to S10a chop
  2716. arrow "" "q\d\s-2\&2\s+2\u,q\d\s-2\&5\s+2\u  " from S10 to S10b chop
  2717. S11a:    box "q\d\s-2\&0\s+2\u" at S11 + ru
  2718. S11b:    box "q\d\s-2\&2\s+2\u" at S11 + rd
  2719. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,     " "    q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" from S11 to S11a chop
  2720. arrow "" "q\d\s-2\&2\s+2\u,q\d\s-2\&5\s+2\u  " from S11 to S11b chop
  2721. S12a:    box "q\d\s-2\&2\s+2\u" at S12 + r
  2722. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,q\d\s-2\&2\s+2\u," "q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u,q\d\s-2\&5\s+2\u" from S12 to S12a chop
  2723. .PE
  2724. .DE 6 "Automaten zur Darstellung der Zustands\*ubergangsfunktionen"
  2725. In Abb. \n($1.6 sind die Automaten dargestellt, die den Feldern von
  2726. Abb. \n($1.5 entsprechen. Die durch Kreise dargestellten Zust\*ande
  2727. werden bei der Abarbeitung der S\*ohne eines Knotens durchlaufen.
  2728. Die durch Quadrate dargestellten Endzust\*ande, stellen das Ergebnis
  2729. der Zustands\*ubergangsfunktion dar.
  2730. .lp
  2731. Es ist unschwer zu erkennen, da\*s die Automaten zum Teil vereinfacht
  2732. werden kann. Offensichtlich sind die Zust\*ande S2, S3, S5 und S6
  2733. \*aquivalent. 
  2734. Das selbe gilt f\*ur S4 und S7. Fa\*st man diese Zust\*ande zusammen
  2735. so erh\*alt man einen reduzierten Automaten (Abb. \n($1.7).
  2736. .DS
  2737. .PS
  2738. circlerad = 0.15i
  2739. boxht = 0.3i
  2740. boxwid = 0.3i
  2741. define r X (1.6i, 0i) X
  2742. define u X (0i, 1.2i) X
  2743. define d X (0i, -1.2i) X
  2744. define ru X (1.6i, 0.4i) X
  2745. define rd X (1.6i, -0.4i) X
  2746. A:    circle invis
  2747. B:    circle invis at A + d
  2748. C:    circle invis at B + d
  2749. S6:    circle "S1" at A + r
  2750. S3:    box "q\d\s-2\&3\s+2\u" at B + r
  2751. S5:    box "q\d\s-2\&5\s+2\u" at C + r
  2752. arrow "'+'" "" from A to S6 chop
  2753. arrow "Const" "" from B to S3 chop
  2754. arrow "Ident" "" from C to S5 chop
  2755. S7:    circle "S2" at S6 + r 
  2756. S9:    circle "S3" at S6 + r + d
  2757. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" "" from S6 to S7 chop
  2758. arrow "q\d\s-2\&2\s+2\u,   q\d\s-2\&5\s+2\u" from S6 to S9 chop
  2759. S7a:    box "q\d\s-2\&0\s+2\u" at S7 + ru
  2760. S7b:    box "q\d\s-2\&2\s+2\u" at S7 + rd
  2761. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,     " "    q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u" from S7 to S7a chop
  2762. arrow "" "q\d\s-2\&2\s+2\u,q\d\s-2\&5\s+2\u  " from S7 to S7b chop
  2763. S9a:    box "q\d\s-2\&2\s+2\u" at S9 + r
  2764. arrow "q\d\s-2\&0\s+2\u,q\d\s-2\&1\s+2\u,q\d\s-2\&2\s+2\u," "q\d\s-2\&3\s+2\u,q\d\s-2\&4\s+2\u,q\d\s-2\&5\s+2\u" from S9 to S9a chop
  2765. .PE
  2766. .DE 7 "reduzierte Automaten zur Berechnung der Zust\*ande"
  2767. Um diese Komprimierung zu erreichen, wird so vorgegangen, da\*s man
  2768. vertr\*agliche Zust\*ande zusammenfa\*st, wobei Zust\*ande dann
  2769. vertr\*aglich sind, wenn sie bei der gleichen Eingabe zum selben
  2770. Zustand f\*uhren. Da sich die Zusammenfassung von Zust\*anden im
  2771. allgemeinen positiv auf die Vertr\*aglichkeit der Vorg\*anger
  2772. auswirkt, sollten dabei alle Nachfolger eines Zustandes auf m\*ogliche
  2773. Vertr\*aglichkeiten untersucht und m\*ogliche Zusammenfassungen
  2774. durchgef\*uhrt sein, bevor der Zustand selbst betrachtet wird.
  2775. .SH 2 "Realisierung der Automaten"
  2776. .lp
  2777. Um den Automaten zu realisieren, werden die zu einem Zustand
  2778. geh\*origen \*Uberg\*ange als eindimensionale Felder
  2779. dargestellt (Abb. \n($1.8).
  2780. .DS
  2781. .TS
  2782. box;
  2783. l|llllll.
  2784.     q\*<0\*>    q\*<1\*>    q\*<2\*>    q\*<3\*>    q\*<4\*>    q\*<5\*>
  2785. _
  2786. S1    S2    S2    S3    S2    S2    S3
  2787. .TE
  2788. .TS
  2789. box;
  2790. l|llllll.
  2791.     q\*<0\*>    q\*<1\*>    q\*<2\*>    q\*<3\*>    q\*<4\*>    q\*<5\*>
  2792. _
  2793. S2    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2794. .TE
  2795. .TS
  2796. box;
  2797. l|llllll.
  2798.     q\*<0\*>    q\*<1\*>    q\*<2\*>    q\*<3\*>    q\*<4\*>    q\*<5\*>
  2799. _
  2800. S3    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>
  2801. .TE    
  2802. .DE 8 "Felder zur Berechnung der Zustands\*uberg\*ange"
  2803. Um den Speicherbedarf f\*ur diese Felder zu reduzieren, werden alle
  2804. in ein gemeinsames Feld eingebettet. Bei diesem unter dem
  2805. Begriff Kammvektortechnik bekannten Verfahren werden soweit m\*oglich
  2806. identische Eintr\*age verschiedener Felder \*uberlagert, und L\*ucken
  2807. in den Feldern durch die Eintr\*age andere Felder gef\*ullt.
  2808. .DS
  2809. .TS
  2810. box;
  2811. lllllllllllllllll.
  2812. S2    S2    S3    S2    S2    S3
  2813.                         q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>
  2814.                                             q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>
  2815. .TE    
  2816. .TS
  2817. box;
  2818. lllllllllllllllll.
  2819. S2    S2    S3    S2    S2    S3    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<0\*>    q\*<0\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>    q\*<2\*>
  2820. .TE    
  2821. .DE 8 "Einbettung des Automaten in ein eindimensionales Feld"
  2822. In unserem Beispiel (Abb. \n($1.9) ist die erzielte Einsparung sehr
  2823. gering, da es keine L\*ucken gibt. Dies liegt daran, da\*s die
  2824. zugrunde gelegte Grammatik extrem einfach ist. Die Klasse (expr), die
  2825. bei der Festlegung der zul\*assigen S\*ohne von '+' verwendet wurde,
  2826. f\*uhrt zu keinerlei Einschr\*ankungen, und somit sind alle
  2827. Zust\*ande f\*ur die S\*ohne m\*oglich (Q\*<expr\*> = Q).
  2828. .lp
  2829. In realistischen Beispielen wird durch diese Ma\*snahme jedoch eine
  2830. drastische Einsparung erzielt, da dort durch Verwendung vieler
  2831. sich gegenseitig ausschlie\*sender Klassen in den einzelnen Felder
  2832. viele L\*ucken entstehen, die bei der Einbettung in ein
  2833. gemeinsames Feld zum Teil geschlossen werden.
  2834. .SH 2 "Vermeidung unn\*otiger Zust\*ande"
  2835. .lp
  2836. In 9.2. wurde festgestellt, da\*s die Bedingungen zur Festlegung der
  2837. Zust\*ande des Baumautomaten nicht hinreichend sind, um sicher zu
  2838. stellen, da\*s nur solche Zust\*ande betrachtet werden, die wirklich
  2839. eintreten k\*onnen. Es gibt jedoch eine M\*oglichkeit, diesen Mangel
  2840. im nachhinein zu beheben.
  2841. .lp
  2842. Offensichtlich ist es so, da\*s die m\*oglichen Zust\*ande
  2843. des Baumautomaten genau den erreichbaren Endzust\*anden der
  2844. Automaten zur Darstellung der \*Ubergangsfunktionen entsprechen.
  2845. Um sie zu erkennen, gen\*ugt es also, die
  2846. erreichbaren Zust\*ande dieser Automaten zu berechnen.
  2847. .SH 2 "Implementierung des Bottom-Up Pattern-Matching"
  2848. .lp
  2849. Neben dem eindimensionalen Feld (yyComb), das die horizontalen Automaten
  2850. beschreibt, wird f\*ur die Realisierung des Pattern-Matching noch
  2851. ein Feld ben\*otigt, das jedem Zustand des Baumautomaten die Menge
  2852. der Vorschriften, deren Muster pa\*st, zuordnet (yySets).
  2853. .lp
  2854. Das Pattern-Matching l\*auft dann f\*ur jeden Knoten c
  2855. folgenderma\*sen ab:
  2856. .np
  2857. state := const\*<c\*>
  2858. .np
  2859. \(fa S\*ohne s\*<i\*> von c
  2860. .br
  2861. state := yyComb [state + yyTraverse (s\*<i\*>)]
  2862. .np
  2863. match := ADR (yySets [state])
  2864. .np
  2865. RETURN state
  2866. .lp
  2867. Zu Beginn (1) wird eine lokale Variable \fIstate\fP mit einem
  2868. knotenspezifischen Wert initialisiert. Die Variable state beschreibt
  2869. sowohl die Zust\*ande des horizontalen Automaten als auch die des
  2870. Baumautomaten. Im zweiten Schritt (2) werden die S\*ohne rekursiv
  2871. abgearbeitet. Gleichzeitig werden, gesteuert durch die Zust\*ande der
  2872. S\*ohne, die von yyTraverse als Ergebnis geliefert werden, die
  2873. \*Uberg\*ange im horizontalen Automaten durchgef\*uhrt.
  2874. Schlie\*slich wird das Ergebnis f\*ur den eigenen Teilbaum, das
  2875. durch die Variable state beschrieben wird, benutzt, um die Vorschriften
  2876. zu bestimmen, deren Muster auf den aktuellen Teilbaum passen (3) und
  2877. anschlie\*send zur\*uckgeliefert (4).
  2878. .lp
  2879. Wenn das Pattern-Matching in die Prozedur yyTraverse, die in Kapitel 6
  2880. beschrieben ist, integriert wird, ergeben sich folgende \*Anderungen.
  2881. .np
  2882. Die Abarbeitung der S\*ohne wird mit der Abarbeitung des horizontalen
  2883. Automaten kombiniert (Punkte (1) und (2) von oben)
  2884. .np
  2885. Die Berechnung der Klassen entf\*allt, da diese beim
  2886. Bottom-Up Pattern-Matching nicht ben\*otigt werden.
  2887. .np
  2888. Um die zul\*assigen Vorschriften zu bestimmen, wird neben den
  2889. Bedingungen lediglich die \*uber die Variable match zug\*angliche
  2890. Menge benutzt (Punkt (3) von oben).
  2891. .np
  2892. Die Prozedur yyTraverse liefert nun einen Zustand als Ergebnis
  2893. zur\*uck (Punkt (4) von oben).
  2894. .lp
  2895. Da Modula-2 keine initialisierte Variablen kennt, m\*ussen au\*serdem
  2896. die Felder yySets und yyComb eingelesen werden, bevor die
  2897. Transformation vorbereitet werden kann.
  2898. .lp
  2899. Die hier beschriebenen Unterschiede k\*onnen im Anhang B.2, der beide
  2900. L\*osungen im Vergleich zeigt, im Detail studiert werden.
  2901. .BP
  2902. .SH 1 "Vollst\*andigkeit"
  2903. .lp
  2904. Eine wesentliche Forderung, die an eine Spezifikation gestellt wird,
  2905. ist die der Voll\%st\*andigkeit. Eine Spezifikation hei\*st
  2906. vollst\*andig, wenn sie geeignet ist, f\*ur
  2907. jede zul\*assige Eingabe die Transformation zu beschreiben.
  2908. .lp
  2909. Die allgemeine Frage, ob eine Spezifikation vollst\*andig ist, ist
  2910. nicht entscheidbar. Im folgenden wird deshalb eine sch\*arfere
  2911. Eigenschaft betrachtet, die die Vollst\*andigkeit impliziert. Obwohl
  2912. auch diese Eigenschaft nicht entscheidbar ist, hilft sie uns einen
  2913. Schritt weiter, denn einzelnen Teile dieser Eigenschaft k\*onnen
  2914. entschieden werden und eignen sich, bestimmte L\*ucken in der
  2915. Vollst\*andigkeit aufzusp\*uren.
  2916. .lp
  2917. Um eine Transformation durchzuf\*uhren, wird die Aufgabe gestellt,
  2918. die Wurzel mit der ersten Funktion der Spezifikation zu bearbeiten.
  2919. Um eine solche Aufgabe zu l\*osen, mu\*s eine passende Vorschrift
  2920. gefunden werden. Funk\%tions\%aufrufe in den Anweisungen dieser
  2921. Vorschrift bilden neue Aufgaben, die ebenfalls bearbeitet werden
  2922. m\*ussen.
  2923. .lp
  2924. Falls man sicherstellen kann, da\*s zur Durchf\*uhrung der
  2925. Transformation nur zul\*assige Aufgaben gestellt werden (Einhaltung
  2926. des Definitionsbereichs), da\*s f\*ur jede zul\*assige Aufgabe
  2927. eine passende Vorschrift existiert (\*Uberdeckung des
  2928. Definitionsbereichs) und da\*s alle zul\*assigen Aufgaben
  2929. abgearbeitet werden k\*onnen (Terminierung), dann ist die
  2930. Spezifikation sicher vollst\*andig.
  2931. .lp
  2932. .SH 2 "Einhaltung des Definitionsbereichs"
  2933. .lp
  2934. Um die Einhaltung des Definitionsbereichs sicherzustellen, mu\*s
  2935. gepr\*uft werden, ob die Teilb\*aume, auf die eine Funktion
  2936. angewandt wird, in den durch den Definitionsbereich festgelegten
  2937. Klassen liegen.
  2938. .lp
  2939. Wenn beim Funktionsaufruf ein Selektor verwendet wird, wird diese
  2940. Pr\*ufung vorgenommen, indem das Teilmuster, das durch den Selektor
  2941. bestimmt ist, analysiert wird. Die Einhaltung des
  2942. Definitionsbereichs ist sichergestellt, falls dieses Teilmuster aus
  2943. einer Klasse des Definitionsbereichs abgeleitet werden kann.
  2944. .lp
  2945. Wird der zu transformierende Baum beim Funktionsaufruf auf
  2946. eine andere Weise festgelegt (z.B. durch eine Variable), kann die
  2947. Einhaltung des Definitionsbereichs nicht automatisch \*uberpr\*uft
  2948. werden, da dann zur Generierungszeit keine M\*oglichkeit besteht, die
  2949. Klassenzugeh\*origkeit dieses Baumes zu bestimmen.
  2950. Der Anwender von ESTRAL wird in solchen F\*allen durch eine Warnung
  2951. auf die Gefahr hingewiesen.
  2952. .SH 2 "\*Uberdeckung des Definitionsbereichs"
  2953. .lp
  2954. Der wesentliche Bestandteil der Vollst\*andigkeitspr\*ufung ist die
  2955. Pr\*ufung, ob der Definitionsbereich durch die Vorschriften abgedeckt
  2956. wird.
  2957. .lp
  2958. Dieser Test wird durchgef\*uhrt, indem jede Klasse (c) des
  2959. Definitionsbereichs (Domain) als (zun\*achst einelementige)
  2960. Menge von synthetisierten Mustern (syn) aufgefa\*st wird und alle
  2961. realen Muster (real) ausgefiltert werden, die durch
  2962. eine Vorschrift abgedeckt werden. Die (in syn) verbliebenen Muster
  2963. k\*onnen mit den Vorschriften nicht bearbeitet werden, sie
  2964. dokumentieren die Unvollst\*andigkeit.
  2965. .lp
  2966. Um die Bedingungen der Vorschriften zu ber\*ucksichtigen,
  2967. werden zwei Durchl\*aufe unterschieden. Im ersten Durchlauf wird
  2968. versucht, mit den Vorschriften auszukommen, die nicht mit einer
  2969. Bedingung verkn\*upft sind. Falls dies nicht gelingt, werden die
  2970. bedingten Vorschriften ebenfalls zum Test herangezogen. Schlie\*slich
  2971. wird f\*ur jedes Muster, das zum Schlu\*s \*ubrig geblieben ist, ein
  2972. Fehler (Error) gemeldet. Muster die erst beim zweiten Durch\%lauf ausgefiltert
  2973. werden, f\*uhren zu einer Warnung (Warning).
  2974. .DS
  2975. Cover
  2976. .HS
  2977. \fBfor\fP \fBall\fP functions f \fBdo\fP
  2978.   \fBfor\fP \fBall\fP c \(mo Domain (f) \fBdo\fP
  2979.     cp := MakePattern (c)
  2980.     syn := EmptyList
  2981.     Append (syn, cp)
  2982.     real := GetUnCondPatterns (f)
  2983.     match := EmptyList
  2984.     Filter (syn, real, match)
  2985.     real := GetCondPatterns (f)
  2986.     match := EmptyList
  2987.     Filter (syn, real, match)
  2988.     \fBwhile\fP \(no IsEmpty (match) \fBdo\fP
  2989.       p := TakeHead (match)
  2990.       Warning ('no unconditional pattern matching', p)
  2991.     \fBwhile\fP \(no IsEmpty (syn) \fBdo\fP
  2992.       p := TakeHead (syn)
  2993.       Error ('no pattern at all matching', p)
  2994. .DE 7 "\*Uberdeckung des Definitionsbereich"
  2995. Zum Filtern (Abb. \n($1.8) wird die Funktion Relation von Abb. 7.6
  2996. herangezogen. Wenn ein synthetisiertes Muster (sp) durch ein reales
  2997. Muster (rp) vollst\*andig \*uberdeckt wird, mu\*s sp nicht
  2998. weiter betrachtet werden. Ist rp nicht geeignet, um sp vollst\*andig
  2999. zu \*uberdecken, mu\*s so vorgegangen werden, da\*s sp durch
  3000. Anwenden der Produktionen der Grammatik durch weitere synthetisierte
  3001. Muster ersetzt wird (Extend), die das urspr\*ungliche
  3002. vollst\*andig beschreiben.
  3003. .lp
  3004. Um diese Erweiterung des synthetisierten Musters (sp) zu unterst\*utzen,
  3005. wird eine Funktion RelationP benutzt. RelationP ist eine Erweiterung von
  3006. Relation, die f\*ur die F\*alle unabh\*angig (independent) und
  3007. gr\*o\*ser (greater) eine Position zur\*uckliefert, an der eine
  3008. sinnvolle Erweiterung ansetzen kann. Mit Hilfe dieser Position und
  3009. anhand der Grammatik wird dann von Extend die Erweiterung,
  3010. d.h. die Synthese von weiteren Mustern durchgef\*uhrt. Die entstandenen
  3011. Muster werden in die Liste syn eingef\*ugt, um im folgenden bearbeitet zu
  3012. werden.
  3013. .lp
  3014. Schlie\*slich wird es m\*oglich sein, einige der generierten Muster
  3015. auszufiltern (match), andere Muster werden \*ubrig bleiben (rest).
  3016. Der Rest bildet den Ausgangspunkt f\*ur den n\*achsten Durchlauf.
  3017. Nach Betrachten aller realen Muster enth\*alt syn alle
  3018. synthetisierten Muster, die nicht durch die realen Muster \*uberdeckt
  3019. werden konnten.
  3020. .DS
  3021. Filter (VAR syn, real, match: tPatternList)
  3022. .HS
  3023. \fBwhile\fP \(no Empty (syn) & \(no Empty (real) \fBdo\fP
  3024.   rest := EmptyList
  3025.   rp := TakeHead (real)
  3026.   \fBwhile\fP \(no Empty (syn) \fBdo\fP
  3027.     sp := TakeHead (syn)
  3028.     \fBcase\fP RelationP (sp, rp, pos) \fBof\fP
  3029.     | equal, less:
  3030.         Append (match, sp)
  3031.     | inconsistent:
  3032.         Append (rest, sp)
  3033.     | independent, greater:
  3034.         \fBif\fP pos = undefined \fBthen\fP
  3035.           Append (rest, sp)
  3036.         \fBelse\fP
  3037.           Extend (sp, pos, syn)
  3038.   syn := rest
  3039. .DE 8 "Filtern von Mustern"
  3040. Abb. \n($1.9 zeigt zwei unabh\*angige Muster, die der Grammatik von Abb. 4.1
  3041. entsprechen, f\*ur die RelationP jedoch keine sinnvolle
  3042. Position zur\*uckliefern kann (pos = undefined).
  3043. .DS
  3044. sp = '+' (:,:)
  3045. rp = const
  3046. .DE 9 "Muster ohne sinnvolle Erweiterung"
  3047. F\*ur die beiden Muster sp und rp existiert keine sinnvolle
  3048. Erweiterung. Zwar w\*urde die Belegung
  3049. der Bl\*atter von sp mit allen M\*oglichkeiten, die durch die Grammatik
  3050. gegeben sind, dazu f\*uhren, da\*s ein Teil der dadurch entstandenen
  3051. Muster ausgefiltert werden kann, doch w\*urden dabei immer neue von rp
  3052. unabh\*angige Muster entstehen, die weiterbearbeitet werden m\*u\*sten.
  3053. Um die Terminierung des Algorithmus an dieser Stelle sicherzustellen,
  3054. wird in solchen F\*allen auf
  3055. eine Erweiterung verzichtet. In pathologischen F\*allen kann das
  3056. zwar dazu f\*uhren, da\*s eine Eingabe irrt\*umlich als unvollst\*andig
  3057. erkannt wird, doch kommt dies in der Praxis kaum vor.
  3058. .SH 2 "Terminierung"
  3059. .lp
  3060. Die Terminierung kann meist dadurch sichergestellt werden, da\*s sich
  3061. die Funktionsaufrufe auf tieferliegende Teilb\*aume beziehen. Da der
  3062. Eingabebaum endlich ist, werden schlie\*slich die Bl\*atter erreicht
  3063. und folglich keine weiteren Funktionen aufgerufen.
  3064. .lp
  3065. Falls sich Funktionsaufrufe hingegen auf den aktuellen Teilbaum
  3066. insgesamt beziehen, wird die Terminierung in Frage gestellt. Denn durch
  3067. einen solchen Funktionsaufruf wird die Terminierung einer Vorschrift
  3068. unmittelbar von der Terminierung der aufgerufenen Funktion abh\*angig.
  3069. Damit entsteht eine Abh\*angigkeiten zwischen Funktionen (aufrufende
  3070. und aufgerufene Funktion). Die Abh\*angigkeit beschr\*ankt sich
  3071. allerdings auf das Muster der be\%tref\%fenden Vorschrift. Au\*serdem ist
  3072. die Abh\*angigkeit nur dann unvermeidbar, wenn es keine andere Vorschrift
  3073. gibt, die alternativ angewandt werden k\*onnte und keine
  3074. Abh\*angigkeit hervorruft. Um unter solchen Bedingungen die
  3075. Terminierung nachzuweisen, m\*u\*ste gezeigt werden, da\*s die
  3076. Entstehung von zyklischen Abh\*angigkeiten vermieden werden kann.
  3077. .lp
  3078. Falls diese Frage \*uberhaupt entscheidbar ist, ist die hierzu
  3079. notwendige Untersuchung auf alle F\*alle \*au\*serst aufwendig.
  3080. Andererseits sind die
  3081. Abh\*angigkeiten zwischen Funktionen in der Praxis recht gering und
  3082. somit auch von Hand zu \*uberschauen. Von ESTRA wird deshalb zum
  3083. Zeitpunkt der Generierung kein Test auf Terminierung durchgef\*uhrt.
  3084. .\"\*([<\*([[Knu68\*(]]\*(>]
  3085. .\"\*([<\*([[MWW84\*(]]\*(>]
  3086. .\"\*([<\*([[Emm88\*(]]\*(>]
  3087. .\"\*([<\*([[HoO82\*(]]\*(>]
  3088. .\"\*([<\*([[Wir85\*(]]\*(>]
  3089. .\"\*([<\*([[KeR83\*(]]\*(>]
  3090. .\"\*([<\*([[BMW87\*(]]\*(>]
  3091. .\"\*([<\*([[Gro89\*(]]\*(>]
  3092. .\"\*([<\*([[AGT87\*(]]\*(>]
  3093. .\"\*([<\*([[MWW84\*(]]\*(>]
  3094. .BP
  3095. .SH 1 "Schnittstellen des Transformators" 9
  3096. .SH 2 "Struktur der Eingabeb\*aume"
  3097. .lp
  3098. Bei der Entwicklung von ESTRA wurde eine Darstellung der
  3099. attributierten B\*aume vorausgesetzt, wie sie von ast\*([<\*([[Gro89\*(]]\*(>] zur
  3100. Verf\*ugung gestellt wird.
  3101. .DS
  3102. .ta 1.5c
  3103. CONST
  3104. .HS
  3105.    Plus    = 1;
  3106.    Const    = 2;
  3107.    Ident    = 3;
  3108. .HS
  3109.    expr    = 4;
  3110.    const    = 5;
  3111.    index    = 6;
  3112.  
  3113. TYPE
  3114. .HS
  3115.    tTree    = POINTER TO tNode;
  3116. .HS
  3117.    yexpr    = RECORD pos: tPosition END;
  3118.    yconst    = RECORD pos: tPosition END;
  3119.    yindex    = RECORD pos: tPosition END;
  3120. .HS
  3121.    yPlus    = RECORD pos: tPosition; lo: tTree; ro: tTree; END;
  3122.    yConst    = RECORD pos: tPosition; value: INTEGER; END;
  3123.    yIdent    = RECORD pos: tPosition; ident: tIdent; END;
  3124. .HS
  3125.    tNode    = RECORD
  3126. .ta 2.5c 4c
  3127.      yyEstraInfo:    ADDRESS;
  3128.      CASE Kind:    INTEGER OF
  3129.      | expr:    expr:    yexpr;
  3130.      | const:    const:    yconst;
  3131.      | index:    index:    yindex;
  3132.      | Plus:    Plus:    yPlus;
  3133.      | Const:    Const:    yConst;
  3134.      | Ident:    Ident:    yIdent;
  3135.      END;
  3136.    END;
  3137. .DE 1 "Darstellung der attributierten B\*aume in Modula-2"
  3138. Die attributierten B\*aume werden als Zeiger auf variante
  3139. Strukturen realisiert (tTree). Die Struktur (tNode) enth\*alt
  3140. f\*ur jede Knotenart und jede Klasse eine Variante. Die g\*ultige
  3141. Variante wird durch das Tag-Feld (Kind) angezeigt.
  3142. .lp
  3143. W\*urde immer \*uber die Variante, die durch das Tag-Feld ausgezeichnet
  3144. ist, auf den Knoten zugegriffen, w\*aren die Varianten, die den
  3145. Klassen entsprechen, \*uberfl\*ussig. Tats\*achlich ist es aber so,
  3146. da\*s diese Varianten benutzt werden, um auf Attribute von S\*ohnen
  3147. zuzugreifen, deren Knotenart nicht feststeht. In unserem Beispiel
  3148. kann auf diese Weise in jedem Knoten auf das Attribut \fIPos\fP
  3149. zugegriffen werden. Damit dies wirklich funktioniert, gen\*ugt es
  3150. nicht, da\*s dieses Attribut in jeder Variante vorkommt, es mu\*s
  3151. auch immer an der selben Stelle stehen. Dies kann im allgemeinen
  3152. sichergestellt werden, wenn die Variante eines Knotens eine
  3153. Erweiterungen der Varianten der
  3154. Klassen darstellen, aus denen er hervorgehen kann.
  3155. .lp
  3156. Das Feld yyEstraInfo dient zur Aufnahme der Attribute, die zur
  3157. Festlegung der Transformation ben\*otigt werden.
  3158. .SH 2 "Schnittstelle des generierten Moduls"
  3159. .lp
  3160. Von ESTRA wird ein Modul generiert, das den Namen der Transformation
  3161. (z.B. Trans) erh\*alt.
  3162. .DS
  3163. .ta 2c
  3164. DEFINITION MODULE Trans;
  3165. .HS
  3166. IMPORT    Tree;
  3167. .HS
  3168. TYPE    tTree = Tree.tTree
  3169. .HS
  3170. (* for bottom-up pattern-matching only *)
  3171. VAR    TransTabName: ARRAY [0..127] OF CHAR;
  3172. .HS
  3173. PROCEDURE BeginTrans;
  3174. PROCEDURE DoTrans (yyt: Tree.tTree);
  3175. PROCEDURE CloseTrans;
  3176. .HS
  3177. END Trans.
  3178. .DE 2 "Schnittstelle des generierten Transformators"
  3179. Die parameterlosen Prozeduren BeginTrans und CloseTrans dienen zur
  3180. Initialisierung und zur Durchf\*uhrung von Abschlu\*sarbeiten.
  3181. DoTrans f\*uhrt die Transformation des Baumes yyt durch. Die
  3182. Schnittstelle von DoTrans entspricht der Schnittstelle der ersten
  3183. Funktion, die in Trans spezifiziert wurde. D.h. falls diese Funktion
  3184. vererbte oder synthetisierte Attribute hat, wird die Schnittstelle von
  3185. DoTrans entsprechend erweitert.
  3186. .lp
  3187. Der Typ tTree, der zur Darstellung der B\*aume verwendet wird, mu\*s
  3188. im EXPORT-Abschnitt bekannt gemacht werden, damit er f\*ur die
  3189. Prozedur DoTrans zur Verf\*ugung steht.
  3190. .lp
  3191. Die Variable TransTabName wird bei Verwendung des Bottom-Up
  3192. Pattern-Matching Al\%go\%rith\%mus benutzt, um den Namen der Tabellendatei
  3193. (hier "Trans.tab") aufzunehmen. Damit besteht die M\*oglichkeit, den
  3194. Namen vor dem Aufruf von BeginTrans zu umzusetzen, falls ein anderer
  3195. Dateiname benutzt werden soll.
  3196. .BP
  3197. .SH 1 "Vergleich mit anderen Werkzeugen"
  3198. .SH 2 "Twig"
  3199. .lp
  3200. Twig\*([<\*([[AGT87\*(]]\*(>] ist ein Werkzeug zur Erstellung von Codegeneratoren.
  3201. Die Beschreibung der Codegeneratoren erfolgt durch Regeln, die
  3202. aus einer Umschreibregel, Kosten und Aktionen, bestehen.
  3203. .lp
  3204. Eine Umschreibregel besteht aus einem Muster und einem Nichtterminal,
  3205. dem sogenannten \fIreplacement node\fP. Das Muster legt fest, wo die
  3206. Regel benutzt werden kann. Nachdem dann die zugeh\*orige Aktion
  3207. ausgef\*uhrt wurde, wird der Teilbaum durch den replacement node
  3208. ersetzt.
  3209. .lp
  3210. Bei der Ausf\*uhrung von Aktionen werden bei Twig verschiedene
  3211. Strategien unterschieden. Neben dem \fItopdown-mode\fP, dessen
  3212. Vorgehensweise der von ESTRA entspricht, kennt Twig noch den
  3213. \fIrewrite-mode\fP und den \fIdeferred-mode\fP. Der
  3214. \fIdeferred-mode\fP entspricht der Postfixstrategie und stellt somit
  3215. lediglich eine Abk\*urzung dar, da die Transformation nicht explizit
  3216. f\*ur die einzelnen S\*ohne aufgerufen werden mu\*s.
  3217. .lp
  3218. Diese Abk\*urzung ist deshalb m\*oglich, weil Twig keine explizite
  3219. Auswahl der Funktionen kennt, mit der die einzelnen Bl\*atter des
  3220. Musters zu bearbeiten sind. Die Bearbeitung der Bl\*atter wird hier
  3221. durch die Nichtterminale im Muster bestimmt. Diese Nichtterminale
  3222. m\*ussen mit den \fIreplacement nodes\fP der zur Transformation der
  3223. Bl\*atter angewandten Regeln
  3224. \*ubereinstimmen. Eine mehrfache Abbildung eines Teilbaums mit
  3225. unterschiedlichen Funktionen, wie ESTRA sie zul\*a\*st, ist folg\%lich
  3226. mit Twig nicht m\*oglich.
  3227. .lp
  3228. Beim \fIrewrite-mode\fP, der von ESTRA nicht unterst\*utzt wird,
  3229. wird der aktuelle Teilbaum durch die Aktion ersetzt und
  3230. anschlie\*send neu bearbeitet. Diese Methode wird bei Twig angeboten,
  3231. obwohl die Gefahr besteht, da\*s es zu einem endlosen Umschreiben
  3232. kommt. Ma\*snahmen zur automatischen Vermeidung eines solchen
  3233. endlosen Umschreibens werden von Twig nicht getroffen (vgl. Kapitel 5).
  3234. .lp
  3235. Der Zugriff auf den Baum erfolgt bei Twig \*uber einen abstrakten
  3236. Datentyp (ADT), wodurch eine weitgehende Unabh\*angigkeit von der
  3237. Darstellung des Baumes erreicht wird.
  3238. .lp
  3239. In ESTRAL wurde auf die Verwendung eines ADTs hingegen verzichtet, um
  3240. den Verlust an Effizienz, der durch die in MODULA-2 notwendige
  3241. Realisierung der Operationen
  3242. als Unterprogramme entsteht, zu vermeiden. Auf der anderen Seite ist
  3243. dadurch die Flexibilit\*at in der Darstellung der B\*aume genommen.
  3244. Dies ist jedoch nicht problematisch, da davon ausgegangen wird,
  3245. da\*s der Anwender von ESTRA bei der Darstellung der B\*aume das
  3246. Werkzeug Ast\*([<\*([[Gro89\*(]]\*(>] zu Hilfe nimmt. Denn das von Ast verwendete Format
  3247. wurde bei der Entwicklung von ESTRA zugrundegelegt und wird somit voll
  3248. unterst\*utzt.
  3249. .lp
  3250. Zur Darstellung der zur Transformation n\*otigen Attribute wird bei
  3251. Twig kein Platz in den Knoten
  3252. des Baumes reserviert. Stattdessen wird eine neuer Baum mit der selben
  3253. Struktur aufgebaut, der diese Attribute sowie Verweise auf die Knoten des
  3254. urspr\*unglichen Baumes aufnimmt.
  3255. .SH 2 "BEG"
  3256. .lp
  3257. BEG (Back End Generator)\*([<\*([[Emm88\*(]]\*(>] ist ein Werkzeug zur automatischen
  3258. Erzeugung effizienter Codegeneratoren. Die Beschreibung erfolgt durch
  3259. Baumersetzungsregeln. 
  3260. .lp
  3261. Eine Baumersetzungsregel beschreibt die Reduktion eines Teilbaumes auf
  3262. ein Nichtterminal. Die Transformation des gesamten Baumes wird durch
  3263. die Reduktion des Baumes auf das Startsymbol bewirkt. Die
  3264. Nichtterminale spielen somit die selbe Rolle wie bereits bei Twig, sie
  3265. stellen sicher, da\*s die Regeln zusammenpassen.
  3266. .lp
  3267. Die einzelnen Regeln k\*onnen hier ebenfalls mit Kosten und
  3268. Bedingungen versehen werden.
  3269. .lp
  3270. Da\*s es sich bei BEG um ein spezielles Werkzeug zur Beschreibung von
  3271. Codegeneratoren handelt, zeigt die Tatsache, da\*s BEG spezielle Mittel
  3272. zur Beschreibung der Registervergabe zur Verf\*ugung stellt.
  3273. .lp
  3274. Au\*serdem beschr\*ankt sich BEG auf die f\*ur die Codeerzeugung
  3275. ausreichende
  3276. Postfixstrategie. Dies hat den Vorteil, da\*s in den Regeln kein
  3277. expliziter Aufruf zur Transformation der S\*ohne erforderlich ist.
  3278. Andererseits ist BEG damit f\*ur allgemeine Transformationen
  3279. unbrauchbar.
  3280. .SH 2 "OPTRAN"
  3281. .lp
  3282. Die Spezifikationssprache OPTRAN\*([<\*([[MWW84\*(]]\*(>] wurde entwickelt, um die
  3283. Transformation attributierter B\*aume zu beschreiben. Da hier
  3284. verlangt wird, da\*s das Ergebnis der Transformation wieder ein
  3285. attributierter Baum ist, k\*onnen die Strukturen der Ein- und Ausgabe
  3286. durch attributierte Grammatiken beschrieben werden.
  3287. .lp
  3288. Zur Beschreibung der Transformation werden Regeln benutzt, die
  3289. die Abbildung eines Eingabe-Musters in ein Ausgabe-Muster festlegen,
  3290. wobei die Regeln so geartet sein m\*ussen, da\*s sie
  3291. entweder innerhalb einer Struktur (Ein- oder Ausgabe) bleiben, oder
  3292. den \*Ubergang von der Eingabe- zur Ausgabe-Struktur beschreiben.
  3293. .lp
  3294. Wie bereits in Kapitel 2 erw\*ahnt wurde, spielt die Reihenfolge, in
  3295. der die Regeln angewandt werden, bei dieser Methode eine entscheidende
  3296. Rolle. In OPTRAN wird deshalb vom Benutzer verlangt, eine Strategie zu
  3297. bestimmen, die diese festlegt.
  3298. .lp
  3299. Im Unterschied zu ESTRA legt OPTRAN besonderen Wert auf die Attributierung.
  3300. Dabei wird zwischen einer Erstattributierung und einer
  3301. Reattributierung unterschieden. Die Erstattributierung dient dazu, vor
  3302. der Transformation die Attribute gem\*a\*s der Eingabe-Grammatik zu
  3303. berechnen. Nach der Transformation mu\*s der Baum gem\*a\*s der
  3304. Ausgabe-Grammatik attributiert sein. Um dies zu erreichen, wird nach
  3305. der Anwendung von Regeln eine Reattributierung durchgef\*uhrt, die
  3306. sicherstellt, da\*s Attribute, die sich aufgrund der Regelanwendung
  3307. ge\*andert haben, neu berechnet werden.
  3308. .BP
  3309. .SH 1 "Zusammenfassung"
  3310. .lp
  3311. Mit ESTRAL wurde eine universelle Spezifikationssprache entwickelt,
  3312. die geeignet ist, beliebige Transformationen attributierter B\*aume
  3313. zu beschreiben.
  3314. .lp
  3315. Durch die Verwendung von Mustern, Bedingungen und Kosten
  3316. k\*onnen Transformationen auf nat\*urliche Weise, d.h. mehrdeutig
  3317. beschrieben werden. Der sequentiellen Natur der Transformation wird
  3318. durch die imperative Beschreibung der einzelnen Vorschriften Rechnung
  3319. getragen.
  3320. .lp
  3321. Um die Beschreibung einer Transformation automatisch in eine
  3322. Implementierung umzusetzen, wurde der Generator ESTRA entwickelt.
  3323. Zur Umsetzung werden von ESTRA zwei Versionen angeboten, die sich in
  3324. Bezug auf das Pattern-Matching unterscheiden.
  3325. .lp
  3326. Zum einen wird ein naives Pattern-Matching angeboten, bei dem jedes
  3327. Muster getrennt betrachtet wird, zum anderen kann auch ein Bottom-Up
  3328. Pattern-Matching, das alle Muster im Zusammenhang sieht, benutzt
  3329. werden. Das Bottom-Up Pattern-Matching zahlt sich insbesondere dann
  3330. aus, wenn bei der Beschreibung der Transformationen viele tiefe
  3331. Muster verwendet werden. Falls es hingegen nur sehr einfache Muster
  3332. gibt, ist das naive Pattern-Matching \*uberlegen.
  3333. .lp
  3334. Erste eigene Eins\*atze von ESTRA haben gezeigt, da\*s
  3335. die in ESTRAL erstellten Spezifikationen in Bezug auf die Wartbarkeit
  3336. deutliche Vorteile gegen\*uber einer direkten Implementierung
  3337. aufweisen. Neben dem h\*oheren Abstraktionsniveau zahlt sich vor allem
  3338. die M\*oglichkeit aus, Spezifikation zu verbessern, in dem man
  3339. Vorschriften hinzuf\*ugt, um Spezialf\*alle zu optimieren.
  3340. .lp
  3341. Zielsprache des Generators ist MODULA-2.
  3342. Erweiterungen des Generators zur Unterst\*utzung anderer
  3343. Programmiersprachen (insbesondere C) wurden aber bereits beim Entwurf
  3344. und der Implementierung des Generators vorbereitet.
  3345. .BP
  3346. .UH 1 "Anhang A: Syntax von ESTRAL"
  3347. .(l L
  3348. .sz -2
  3349. .ta 8 10 30
  3350. transformation    \(eq    \fBTRANSFORMATION\fP
  3351.           ident    \fIName der Transformation\fP
  3352.           [ \fBEXPORT\fP '{' source_text '}' ]    \fI\*offentliche Vereinbarungen\fP
  3353.           [ \fBGLOBAL\fP '{' source_text '}' ]    \fIglobale Vereinbarungen\fP
  3354.           [ \fBBEGIN\fP '{' source_text '}' ]    \fIAnweisungen zur Initialisierung\fP
  3355.           [ \fBCLOSE\fP '{' source_text '}' ]    \fIAnweisungen zum Abschlu\*s\fP
  3356.           grammar    \fIBaumgrammatik\fP
  3357.           function *    \fIFunktionen\fP
  3358. .HS
  3359. grammar    \(eq    \fBGRAMMAR\fP
  3360.           ident    \fIName der Grammatik\fP
  3361.           production *    \fIKlassen\fP
  3362. .HS
  3363. production    \(eq    class    \fIKlasse\fP
  3364.           node *    \fIKnotenbeschreibungen\fP
  3365. .HS
  3366. class    \(eq    [ ident '\(mi>' ]    \fIBezeichner der Oberklasse\fP
  3367.           ident '='    \fIBezeichner der Klasse\fP
  3368. .HS
  3369. node    \(eq    '\(or' (string \(or ident)    \fIName des Knotens\fP
  3370.           [ ':'ident ]    \fIBezeichner des Knotens\fP
  3371.           '(' [ son \(or\(or ',' ] ')'    \fIS\*ohne\fP
  3372. .HS
  3373. son    \(eq    [ ident ':' ]    \fIName des Sohnes\fP
  3374.         ident    \fIBezeichner der Klasse des Sohnes\fP
  3375. .HS
  3376. function    \(eq    \fBFUNCTION\fP
  3377.           ident    \fIName der Funktion\fP
  3378.           [attributes    \fIvererbte Attribute\fP
  3379.            '\(mi>'
  3380.            attributes]    \fIsynthetisierte Attribute\fP
  3381.           [':' type]    \fIErgebnistyp\fP
  3382.           domain    \fIDefinitionsbereich\fP
  3383.           directive *    \fIVorschriften zur Beschreibung der Funktion\fP
  3384. .HS
  3385. attributes    \(eq    [ (ident \(or\(or ','    \fIListe von Bezeichnern\fP
  3386.           ':' type)    \fIAngabe des Typs\fP
  3387.           \(or\(or ';' ]    \fImehrere solche Listen durch ';' getrennt\fP
  3388. .HS
  3389. type    \(eq    [ ident '.' ]    \fIAngabe des Moduls zur Qualifikation\fP
  3390.           ident    \fIBezeichner des Typs\fP
  3391. .HS
  3392. domain    \(eq    '/' ident \(or\(or ',' '/'    \fIListe von Klassenbezeichnern\fP
  3393. .HS
  3394. directive    \(eq    pattern    \fIMuster\fP
  3395.           [ \fBCONDITION\fP '{' source_text '}' ]    \fIBedingung\fP
  3396.           [ \fBCOSTS\fP (number \(or '{' source_text '}') ]    \fIKosten\fP
  3397.           [ \fBDECLARE\fP '{' source_text '}' ]    \fIlokale Vereinbarungen\fP
  3398.           '{' source_text '}'    \fIAnweisungen zur Umsetzung\fP
  3399. .HS
  3400. pattern    \(eq    [ ident ] ':'    \fI Selektor\fP
  3401.           [ ident ]    \fIBezeichner der Klasse\fP
  3402. .HS
  3403.     \(or    ident    \fISelektor und Bezeichner der Klasse\fP
  3404. .HS
  3405.     \(or    [ [ ident ] ':' ]    \fISelektor\fP
  3406.           (ident \(or string)    \fIName des Knotens\fP
  3407.           '(' [ pattern \(or\(or ',' ] ')'    \fIMuster der S\*ohne\fP
  3408. .)l
  3409. .BP
  3410. .UH 1 "Anhang B: Beispiel f\*ur die Anwendung von ESTRA"
  3411. .UH 2 "Anhang B1: Spezifikation in ESTRAL"
  3412. .(l L
  3413. .sz -2
  3414. .ta 5 10 15 20 25 30 35 40 45
  3415. TRANSFORMATION Trans
  3416. .HS
  3417. /*
  3418.  *    Quelltexterzeugung und Konstantenfaltung:
  3419.  *    - es wird MODULA-2 Quelltext ausgegeben
  3420.  *    - arithmetische und boolesche Konstanten werden gefaltet
  3421.  */
  3422. .HS
  3423. EXPORT    {
  3424. FROM    Tree    IMPORT    tTree;
  3425. }
  3426. .HS
  3427. GLOBAL    {
  3428. FROM    StdIO    IMPORT    BeginIO, CloseIO, WriteS, WriteI, WriteNl, WriteIdent;
  3429. FROM    Tree    IMPORT    tTree;
  3430. }
  3431. .HS
  3432. BEGIN    {
  3433. BeginIO;
  3434. }
  3435. .HS
  3436. CLOSE    {
  3437. CloseIO;
  3438. }
  3439. .HS
  3440. .HS
  3441. .HS
  3442. GRAMMAR    Tree
  3443. .HS
  3444. .HS
  3445. /* statements */
  3446. .HS
  3447. stats    =
  3448. | Stats        (stat, stats)
  3449. | Stats0    ()
  3450. .HS
  3451. stat    =
  3452. | If        (bExpr, then: stats, else: stats)
  3453. | ':=':    Assign    (index, aExpr)
  3454. .HS
  3455. .HS
  3456. /* arithmetic expressions */
  3457. .HS
  3458. aExpr    =    
  3459. | '+':    Plus    (lo: aExpr, ro: aExpr)
  3460. .HS
  3461. aExpr    ->
  3462. index    =
  3463. | aIdent    ()
  3464. .HS
  3465. aExpr    ->
  3466. aConst    =
  3467. | Const        ()
  3468. | '+'        (aConst, aConst)
  3469. .HS
  3470. .HS
  3471. /* boolean expressions */
  3472. .HS
  3473. bExpr    =
  3474. | '<': Less    (lo: aExpr, ro: aExpr)
  3475. | bIdent    ()
  3476. .HS
  3477. bExpr    ->
  3478. bConst    =
  3479. | True        ()
  3480. | False        ()
  3481. | '<'        (aConst, aConst)
  3482. .HS
  3483. .HS
  3484. .HS
  3485. FUNCTION    Code            /stats, stat, aExpr, bExpr/
  3486. .HS
  3487. /*    Ausgabe von MODULA-2 Quelltext        */
  3488. .HS
  3489. /* statements */
  3490. .HS
  3491. Stats    (stat, stats)                COSTS    1
  3492. .HS
  3493. {    Code    (stat);
  3494.     WriteS    (';'); WriteNl;
  3495.     Code    (stats);            }
  3496. .HS
  3497. .HS
  3498. Stats0    ()                COSTS    0
  3499. .HS
  3500. {}
  3501. .HS
  3502. .HS
  3503. If    (bConst, then: stats, else: stats)        CONDITION { BFold (bConst) = TRUE }
  3504.                             COSTS    0
  3505. .HS
  3506. {    Code    (then);            }
  3507. .HS
  3508. .HS
  3509. If    (bConst, then: stats, else: stats)        CONDITION { BFold (bConst) = FALSE }
  3510.                             COSTS    0
  3511. .HS
  3512. {    Code    (else);            }
  3513. .HS
  3514. .HS
  3515. If    (bExpr, then: stats, else: Stats0 ())        COSTS    3
  3516. .HS
  3517. {    WriteS    ('IF ');
  3518.     Code    (bExpr);
  3519.     WriteS    (' THEN'); WriteNl;
  3520.     Code    (then);
  3521.     WriteS    (' END;');            }
  3522. .HS
  3523. .HS
  3524. If    (bExpr, then: Stats0 (), else: stats )        COSTS    3
  3525. .HS
  3526. {    WriteS    ('IF NOT (');
  3527.     Code    (bExpr);
  3528.     WriteS    (') THEN'); WriteNl;
  3529.     Code    (else);
  3530.     WriteS    (' END;');            }
  3531. .HS
  3532. .HS
  3533. If    (bExpr, then: stats, else: stats)        COSTS    4
  3534. .HS
  3535. {    WriteS    ('IF ');
  3536.     Code    (bExpr);
  3537.     WriteS    (' THEN'); WriteNl;
  3538.     Code    (then);
  3539.     WriteS    (' ELSE'); WriteNl;
  3540.     Code    (else);
  3541.     WriteS    (' END;');            }
  3542. .HS
  3543. .HS
  3544. \&':='    (index, aExpr)            COSTS    1
  3545. .HS
  3546. {    Code    (index);
  3547.     WriteS    (' := ');
  3548.     Code    (aExpr);            }
  3549. .HS
  3550. .HS
  3551. /* arithmetic expressions */
  3552. .HS
  3553. \&'+'    (lo: aExpr, ro: aExpr)            COSTS    1
  3554. .HS
  3555. {    WriteS    ('( ');
  3556.     Code    (lo);
  3557.     WriteS    (' + ');
  3558.     Code    (ro);
  3559.     WriteS    (' )');            }
  3560. .HS
  3561. .HS
  3562. aConst                    COSTS    1
  3563. .HS
  3564. {    WriteI    (AFold (aConst));        }
  3565. .HS
  3566. .HS
  3567. aIdent    ()                COSTS    1
  3568. .HS
  3569. {    WriteIdent    (aIdent.ident);        }
  3570. .HS
  3571. .HS
  3572. \&'<'    (lo:aExpr, ro:aExpr)            COSTS    1
  3573. .HS
  3574. {    WriteS    ('( ');
  3575.     Code    (lo);
  3576.     WriteS    (' < ');
  3577.     Code    (ro);
  3578.     WriteS    (')');            }
  3579. .HS
  3580. .HS
  3581. bIdent    ()                COSTS    1
  3582. .HS
  3583. {    WriteIdent    (bIdent.ident);        }
  3584. .HS
  3585. .HS
  3586. bConst                    COSTS    1
  3587. .HS
  3588. {    IF BFold (bConst) THEN
  3589.       WriteS    ('TRUE');
  3590.     ELSE
  3591.       WriteS    ('FALSE');
  3592.     END;                }
  3593. .HS
  3594. .HS
  3595. .HS
  3596. FUNCTION    AFold     : INTEGER    /aConst/
  3597. .HS
  3598. /*    Faltung arithmetischer Konstanten        */
  3599. .HS
  3600. .HS
  3601. Const    ()                COSTS    0
  3602. .HS
  3603. {    RETURN Const.value;            }
  3604. .HS
  3605. .HS
  3606. \&'+'    (lo:aConst, ro:aConst)            COSTS    0
  3607. .HS
  3608. {    RETURN AFold (lo) + AFold (ro);    }
  3609. .HS
  3610. .HS
  3611. .HS
  3612. FUNCTION    BFold     : BOOLEAN    /bConst/
  3613. .HS
  3614. /*    Faltung boolescher Konstanten        */
  3615. .HS
  3616. .HS
  3617. True    ()                COSTS    0
  3618. .HS
  3619. {    RETURN TRUE;            }
  3620. .HS
  3621. .HS
  3622. False    ()                COSTS    0
  3623. .HS
  3624. {    RETURN FALSE;            }
  3625. .HS
  3626. .HS
  3627. \&'<'    (lo: aConst, ro: aConst)            COSTS    0
  3628. .HS
  3629. {    RETURN AFold (lo) < AFold (ro);    }
  3630. .)l
  3631. .oh ''%''
  3632. .bp
  3633. .UH 2 "Anhang B2: Generierter Code"
  3634. .lp
  3635. Im folgenden ist der von ESTRA generierte Code dargestellt.
  3636. .lp
  3637. Die Unterschiede, der beiden Versionen, die durch den optionalen Einsatz
  3638. des Bottom-Up Pattern-Matching entstehen, werden so dargestellt,
  3639. da\*s der Leser diese unmittelbar vergleichen kann.
  3640. .(l L
  3641. .sz -2
  3642. (* ------ simple pattern-matching ------
  3643.    (A)
  3644.    --------------------------------------------- *)
  3645.    (B)
  3646. (* --- bottom-up pattern-matching --- *)
  3647. Beim Einsatz des Bottom-Up Pattern-Matching wird (B) generiert,
  3648. ansonsten wird (A) erzeugt.
  3649. .sp 8
  3650. .)l
  3651. .(l L
  3652. .sz -2
  3653. .ta 5 10 15 20 25 30 35 40 45
  3654. DEFINITION MODULE Trans;
  3655. .HS
  3656. IMPORT Tree;
  3657.     (* line 3 Trans.estra *)
  3658. .HS
  3659. FROM    Tree    IMPORT    tTree;
  3660. .HS
  3661. (* ------ simple pattern-matching ------
  3662.    --------------------------------------------- *)
  3663. VAR TransTabName: ARRAY [0..127] OF CHAR;
  3664. (* --- bottom-up pattern-matching --- *)
  3665. .HS
  3666. PROCEDURE BeginTrans;
  3667. PROCEDURE DoTrans (yyt: Tree.tTree);
  3668. PROCEDURE CloseTrans;
  3669. END Trans.
  3670. .)l
  3671. .bp
  3672. .(l L
  3673. .sz -2
  3674. .ta 5 10 15 20 25 30 35 40 45
  3675. IMPLEMENTATION MODULE Trans;
  3676. .HS
  3677. (* ------ simple pattern-matching ------
  3678. IMPORT SYSTEM, IO, Memory, Tree;
  3679.    --------------------------------------------- *)
  3680. IMPORT SYSTEM, IO, Memory, SystemIO, Tree;
  3681. (* --- bottom-up pattern-matching --- *)
  3682. .HS
  3683.     (* line 7 Trans.estra *)
  3684. .HS
  3685. FROM    StdIO    IMPORT    BeginIO, CloseIO, WriteS, WriteI, WriteNl, WriteIdent;
  3686. FROM    Tree    IMPORT    tTree;
  3687. .HS
  3688. .HS
  3689. CONST
  3690.   yyInfinite = 2147483643;
  3691. .HS
  3692.   yyBitsPerBitset = 32;
  3693. (* ------ simple pattern-matching ------
  3694.   yyCstats = 0;
  3695.   yyCstat = 1;
  3696.   yyCbExpr = 5;
  3697.   yyCindex = 3;
  3698.   yyCaExpr = 2;
  3699.   yyCaConst = 4;
  3700.   yyCbConst = 6;
  3701.   yyMaxClass = 6;
  3702.    --------------------------------------------- *)
  3703.   yySetSize = 22;
  3704.   yyMaxIndex = 26;
  3705.   yyCombSize = 117;      
  3706.   yyStartState = 0;
  3707. (* --- bottom-up pattern-matching --- *)
  3708. .HS
  3709.   yyPoolSize = 10240;
  3710. .HS
  3711. TYPE
  3712.   yytBlockPtr = POINTER TO yytBlock;
  3713.   yytBlock =
  3714.   RECORD
  3715.     Successor: yytBlockPtr;
  3716.     Block: ARRAY [1..yyPoolSize] OF CHAR;
  3717.   END;
  3718. .HS
  3719. (* ------ simple pattern-matching ------
  3720.    --------------------------------------------- *)
  3721.   yyStateType = INTEGER;
  3722.   yySetType = ARRAY [0..yySetSize DIV yyBitsPerBitset] OF BITSET;
  3723.   yySetsType = ARRAY [0..yyMaxIndex] OF yySetType;
  3724.   yyCombType = ARRAY [0..yyCombSize] OF yyStateType;
  3725. .HS
  3726. (* --- bottom-up pattern-matching --- *)
  3727.   yyPCode = PROCEDURE (Tree.tTree);
  3728.   yyPAFold = PROCEDURE (Tree.tTree): INTEGER;
  3729.   yyPBFold = PROCEDURE (Tree.tTree): BOOLEAN;
  3730. .HS
  3731.   yyInfoPtr  = POINTER TO yyInfoType;
  3732.   yyInfoType =
  3733.     RECORD
  3734. (* ------ simple pattern-matching ------
  3735.       yyClasses: ARRAY [0..yyMaxClass DIV yyBitsPerBitset] OF BITSET;
  3736.    --------------------------------------------- *)
  3737. (* --- bottom-up pattern-matching --- *)
  3738.       Code: RECORD Cost: INTEGER; Proc: yyPCode; END;
  3739.       AFold: RECORD Cost: INTEGER; Proc: yyPAFold; END;
  3740.       BFold: RECORD Cost: INTEGER; Proc: yyPBFold; END;
  3741.     END;
  3742. .HS
  3743. VAR
  3744.   yySets: yySetsType;
  3745.   yyComb: yyCombType;
  3746.   yyInfo: yyInfoType;
  3747.   yyMatch: ARRAY [0..22] OF BOOLEAN;
  3748.   yyBlockList: yytBlockPtr;
  3749.   yyPoolFreePtr, yyPoolEndPtr: SYSTEM.ADDRESS;
  3750. .HS
  3751. (* ------ simple pattern-matching ------
  3752. PROCEDURE yyClass (yyt: Tree.tTree;Bit, Set: INTEGER): BOOLEAN;
  3753. VAR info: yyInfoPtr;
  3754. BEGIN
  3755.   info := yyt^.yyEstraInfo;
  3756.   RETURN Bit IN info^.yyClasses [Set];
  3757. END yyClass;
  3758. .HS
  3759.    --------------------------------------------- *)
  3760. (* --- bottom-up pattern-matching --- *)
  3761. PROCEDURE yyAlloc (): SYSTEM.ADDRESS;
  3762. VAR BlockPtr: yytBlockPtr;
  3763. BEGIN
  3764.   IF LONGINT (yyPoolEndPtr - yyPoolFreePtr) < SYSTEM.TSIZE (yyInfoType) THEN
  3765.     BlockPtr  := yyBlockList;
  3766.     yyBlockList  := Memory.Alloc (SYSTEM.TSIZE (yytBlock));
  3767.     yyBlockList^.Successor := BlockPtr;
  3768.     yyPoolFreePtr := SYSTEM.ADR (yyBlockList^.Block);
  3769.     yyPoolEndPtr  := yyPoolFreePtr + yyPoolSize;
  3770.   END;
  3771.   INC (yyPoolFreePtr, SYSTEM.ADDRESS (SYSTEM.TSIZE (yyInfoType)));
  3772.   RETURN yyPoolFreePtr - SYSTEM.ADDRESS (SYSTEM.TSIZE (yyInfoType));
  3773. END yyAlloc;
  3774. .HS
  3775. PROCEDURE yyReleaseHeap;
  3776. VAR BlockPtr: yytBlockPtr;
  3777. BEGIN
  3778.   WHILE yyBlockList # NIL DO
  3779.     BlockPtr:= yyBlockList;
  3780.     yyBlockList:= yyBlockList^.Successor;
  3781.     Memory.Free (SYSTEM.TSIZE (yytBlock), BlockPtr);
  3782.   END;
  3783. END yyReleaseHeap;
  3784. .HS
  3785. PROCEDURE Code (yyt: Tree.tTree);
  3786. VAR InfoPtr: yyInfoPtr;
  3787. BEGIN
  3788.   InfoPtr := yyInfoPtr (yyt^.yyEstraInfo);
  3789.   InfoPtr^.Code.Proc (yyt);
  3790. END Code;
  3791. .HS
  3792. PROCEDURE AFold (yyt: Tree.tTree): INTEGER;
  3793. VAR InfoPtr: yyInfoPtr;
  3794. BEGIN
  3795.   InfoPtr := yyInfoPtr (yyt^.yyEstraInfo);
  3796.   RETURN InfoPtr^.AFold.Proc (yyt);
  3797. END AFold;
  3798. .HS
  3799. PROCEDURE BFold (yyt: Tree.tTree): BOOLEAN;
  3800. VAR InfoPtr: yyInfoPtr;
  3801. BEGIN
  3802.   InfoPtr := yyInfoPtr (yyt^.yyEstraInfo);
  3803.   RETURN InfoPtr^.BFold.Proc (yyt);
  3804. END BFold;
  3805. .HS
  3806. PROCEDURE yyECode (yyt: Tree.tTree);
  3807. BEGIN
  3808.   IO.WriteS (IO.StdError, 'Function Code is not defined for this tree');
  3809.   IO.WriteNl (IO.StdError); IO.CloseIO; HALT;
  3810. END yyECode;
  3811. .HS
  3812. PROCEDURE yyEAFold (yyt: Tree.tTree): INTEGER;
  3813. BEGIN
  3814.   IO.WriteS (IO.StdError, 'Function AFold is not defined for this tree');
  3815.   IO.WriteNl (IO.StdError); IO.CloseIO; HALT;
  3816. END yyEAFold;
  3817. .HS
  3818. PROCEDURE yyEBFold (yyt: Tree.tTree): BOOLEAN;
  3819. BEGIN
  3820.   IO.WriteS (IO.StdError, 'Function BFold is not defined for this tree');
  3821.   IO.WriteNl (IO.StdError); IO.CloseIO; HALT;
  3822. END yyEBFold;
  3823. .HS
  3824. PROCEDURE yyF1Code (yyt: Tree.tTree);
  3825. .HS
  3826. BEGIN    (* line 72 Trans.estra *)
  3827.     Code    (yyt^.Stats.stat);
  3828.     WriteS    (';'); WriteNl;
  3829.     Code    (yyt^.Stats.stats);            
  3830. END yyF1Code;
  3831. .HS
  3832. PROCEDURE yyF2Code (yyt: Tree.tTree);
  3833. .HS
  3834. BEGIN
  3835. END yyF2Code;
  3836. .HS
  3837. PROCEDURE yyF3Code (yyt: Tree.tTree);
  3838. .HS
  3839. BEGIN    (* line 90 Trans.estra *)
  3840.     Code    (yyt^.If.then);                
  3841. END yyF3Code;
  3842. .HS
  3843. PROCEDURE yyF4Code (yyt: Tree.tTree);
  3844. .HS
  3845. BEGIN    (* line 99 Trans.estra *)
  3846.     Code    (yyt^.If.else);                
  3847. END yyF4Code;
  3848. .HS
  3849. PROCEDURE yyF5Code (yyt: Tree.tTree);
  3850. .HS
  3851. BEGIN
  3852. END yyF5Code;
  3853. .HS
  3854. PROCEDURE yyF6Code (yyt: Tree.tTree);
  3855. .HS
  3856. BEGIN    (* line 113 Trans.estra *)
  3857.     WriteS    ('IF ');
  3858.     Code    (yyt^.If.bExpr);
  3859.     WriteS    (' THEN'); WriteNl;
  3860.     Code    (yyt^.If.then);
  3861.     WriteS    (' END;');            
  3862. END yyF6Code;
  3863. .HS
  3864. PROCEDURE yyF7Code (yyt: Tree.tTree);
  3865. .HS
  3866. BEGIN    (* line 124 Trans.estra *)
  3867.     WriteS    ('IF NOT (');
  3868.     Code    (yyt^.If.bExpr);
  3869.     WriteS    (') THEN'); WriteNl;
  3870.     Code    (yyt^.If.else);
  3871.     WriteS    (' END;');            
  3872. END yyF7Code;
  3873. .HS
  3874. PROCEDURE yyF8Code (yyt: Tree.tTree);
  3875. .HS
  3876. BEGIN    (* line 135 Trans.estra *)
  3877.     WriteS    ('IF ');
  3878.     Code    (yyt^.If.bExpr);
  3879.     WriteS    (' THEN'); WriteNl;
  3880.     Code    (yyt^.If.then);
  3881.     WriteS    (' ELSE'); WriteNl;
  3882.     Code    (yyt^.If.else);
  3883.     WriteS    (' END;');            
  3884. END yyF8Code;
  3885. .HS
  3886. PROCEDURE yyF9Code (yyt: Tree.tTree);
  3887. .HS
  3888. BEGIN    (* line 148 Trans.estra *)
  3889.     Code    (yyt^.Assign.index);
  3890.     WriteS    (' := ');
  3891.     Code    (yyt^.Assign.aExpr);            
  3892. END yyF9Code;
  3893. .HS
  3894. PROCEDURE yyF10Code (yyt: Tree.tTree);
  3895. .HS
  3896. BEGIN    (* line 157 Trans.estra *)
  3897.     WriteS    ('( ');
  3898.     Code    (yyt^.Plus.lo);
  3899.     WriteS    (' + ');
  3900.     Code    (yyt^.Plus.ro);
  3901.     WriteS    (' )');                
  3902. END yyF10Code;
  3903. .HS
  3904. PROCEDURE yyF11Code (yyt: Tree.tTree);
  3905. .HS
  3906. BEGIN    (* line 168 Trans.estra *)
  3907.     WriteI    (yyt^.Const.value);            
  3908. END yyF11Code;
  3909. .HS
  3910. PROCEDURE yyF12Code (yyt: Tree.tTree);
  3911. .HS
  3912. BEGIN    (* line 175 Trans.estra *)
  3913.     WriteS    ('( ');
  3914.     Code    (yyt^.Plus.lo);
  3915.     WriteS    (' + ');
  3916.     Code    (yyt^.Plus.ro);
  3917.     WriteS    (' )');                
  3918. END yyF12Code;
  3919. .HS
  3920. PROCEDURE yyF13Code (yyt: Tree.tTree);
  3921. .HS
  3922. BEGIN    (* line 186 Trans.estra *)
  3923.     WriteIdent    (yyt^.aIdent.ident);        
  3924. END yyF13Code;
  3925. .HS
  3926. PROCEDURE yyF14Code (yyt: Tree.tTree);
  3927. .HS
  3928. BEGIN    (* line 193 Trans.estra *)
  3929.     WriteS    ('TRUE');            
  3930. END yyF14Code;
  3931. .HS
  3932. PROCEDURE yyF15Code (yyt: Tree.tTree);
  3933. .HS
  3934. BEGIN    (* line 200 Trans.estra *)
  3935.     WriteS    ('FALSE');            
  3936. END yyF15Code;
  3937. .HS
  3938. PROCEDURE yyF16Code (yyt: Tree.tTree);
  3939. .HS
  3940. BEGIN    (* line 207 Trans.estra *)
  3941.     WriteS    ('( ');
  3942.     Code    (yyt^.Less.lo);
  3943.     WriteS    (' < ');
  3944.     Code    (yyt^.Less.ro);
  3945.     WriteS    (')');                
  3946. END yyF16Code;
  3947. .HS
  3948. PROCEDURE yyF17Code (yyt: Tree.tTree);
  3949. .HS
  3950. BEGIN    (* line 218 Trans.estra *)
  3951.     WriteIdent    (yyt^.bIdent.ident);        
  3952. END yyF17Code;
  3953. .HS
  3954. PROCEDURE yyF18AFold (yyt: Tree.tTree): INTEGER;
  3955. .HS
  3956. BEGIN    (* line 229 Trans.estra *)
  3957.     RETURN yyt^.Const.value;            
  3958. END yyF18AFold;
  3959. .HS
  3960. PROCEDURE yyF19AFold (yyt: Tree.tTree): INTEGER;
  3961. .HS
  3962. BEGIN    (* line 236 Trans.estra *)
  3963.     RETURN AFold (yyt^.Plus.lo) + AFold (yyt^.Plus.ro);        
  3964. END yyF19AFold;
  3965. .HS
  3966. PROCEDURE yyF20BFold (yyt: Tree.tTree): BOOLEAN;
  3967. .HS
  3968. BEGIN    (* line 247 Trans.estra *)
  3969.     RETURN TRUE;                
  3970. END yyF20BFold;
  3971. .HS
  3972. PROCEDURE yyF21BFold (yyt: Tree.tTree): BOOLEAN;
  3973. .HS
  3974. BEGIN    (* line 254 Trans.estra *)
  3975.     RETURN FALSE;                
  3976. END yyF21BFold;
  3977. .HS
  3978. PROCEDURE yyF22BFold (yyt: Tree.tTree): BOOLEAN;
  3979. .HS
  3980. BEGIN    (* line 261 Trans.estra *)
  3981.     RETURN AFold (yyt^.Less.lo) < AFold (yyt^.Less.ro);        
  3982. END yyF22BFold;
  3983. .HS
  3984. PROCEDURE CostCode (yyt: Tree.tTree): INTEGER;
  3985. VAR
  3986.   InfoPtr: yyInfoPtr;
  3987. BEGIN
  3988.   InfoPtr := yyt^.yyEstraInfo;
  3989.   RETURN InfoPtr^.Code.Cost;
  3990. END CostCode;
  3991. .HS
  3992. PROCEDURE CostAFold (yyt: Tree.tTree): INTEGER;
  3993. VAR
  3994.   InfoPtr: yyInfoPtr;
  3995. BEGIN
  3996.   InfoPtr := yyt^.yyEstraInfo;
  3997.   RETURN InfoPtr^.AFold.Cost;
  3998. END CostAFold;
  3999. .HS
  4000. PROCEDURE CostBFold (yyt: Tree.tTree): INTEGER;
  4001. VAR
  4002.   InfoPtr: yyInfoPtr;
  4003. BEGIN
  4004.   InfoPtr := yyt^.yyEstraInfo;
  4005.   RETURN InfoPtr^.BFold.Cost;
  4006. END CostBFold;
  4007. .HS
  4008. (* ------ simple pattern-matching ------
  4009. PROCEDURE yyTraverse (yyt: Tree.tTree);
  4010.    --------------------------------------------- *)
  4011. PROCEDURE yyTraverse (yyt: Tree.tTree): yyStateType;
  4012. (* --- bottom-up pattern-matching --- *)
  4013. VAR
  4014.   state: yyStateType;
  4015.   match: POINTER TO yySetType;
  4016.   cost: INTEGER;
  4017.   info: yyInfoPtr;
  4018.   success: BOOLEAN;
  4019. .HS
  4020. BEGIN
  4021.   info := yyAlloc ();
  4022.   info^ := yyInfo;
  4023.   yyt^.yyEstraInfo := info;
  4024. .HS
  4025. .HS
  4026.   CASE yyt^.Kind OF
  4027. .HS
  4028.   | Tree.Stats:
  4029. (* ------ simple pattern-matching ------
  4030.       yyTraverse (yyt^.Stats.stat);
  4031.       yyTraverse (yyt^.Stats.stats);
  4032.       INCL (info^.yyClasses [yyCstats DIV yyBitsPerBitset], yyCstats MOD yyBitsPerBitset); 
  4033.    --------------------------------------------- *)
  4034.       state := 0;
  4035.       state := yyComb [state + yyTraverse (yyt^.Stats.stat)];
  4036.       state := yyComb [state + yyTraverse (yyt^.Stats.stats)];
  4037. (* --- bottom-up pattern-matching --- *)
  4038. .HS
  4039. .HS
  4040.       cost := 1
  4041.       + CostCode (yyt^.Stats.stat)
  4042.       + CostCode (yyt^.Stats.stats);
  4043.       IF cost < info^.Code.Cost THEN
  4044.         info^.Code.Cost := cost;
  4045.         info^.Code.Proc := yyF1Code;
  4046.       END;
  4047. .HS
  4048.   | Tree.Stats0:
  4049. (* ------ simple pattern-matching ------
  4050.       INCL (info^.yyClasses [yyCstats DIV yyBitsPerBitset], yyCstats MOD yyBitsPerBitset); 
  4051.    --------------------------------------------- *)
  4052.       state := 1;
  4053. (* --- bottom-up pattern-matching --- *)
  4054. .HS
  4055. .HS
  4056.       cost := 0;
  4057.       IF cost < info^.Code.Cost THEN
  4058.         info^.Code.Cost := cost;
  4059.         info^.Code.Proc := yyF2Code;
  4060.       END;
  4061. .HS
  4062.   | Tree.If:
  4063. (* ------ simple pattern-matching ------
  4064.       yyTraverse (yyt^.If.bExpr);
  4065.       yyTraverse (yyt^.If.then);
  4066.       yyTraverse (yyt^.If.else);
  4067.       INCL (info^.yyClasses [yyCstat DIV yyBitsPerBitset], yyCstat MOD yyBitsPerBitset); 
  4068. .HS
  4069.       yyMatch [3] := yyClass (yyt^.If.bExpr, yyCbConst MOD yyBitsPerBitset, yyCbConst DIV yyBitsPerBitset)
  4070.       & (          (* line 86 Trans.estra *)
  4071.     BFold (yyt^.If.bExpr) = TRUE     );
  4072.       yyMatch [4] := yyClass (yyt^.If.bExpr, yyCbConst MOD yyBitsPerBitset, yyCbConst DIV yyBitsPerBitset)
  4073.       & (          (* line 95 Trans.estra *)
  4074.     BFold (yyt^.If.bExpr) = FALSE     );
  4075.       yyMatch [5] := (yyt^.If.then^.Kind = Tree.Stats0)
  4076.        & (yyt^.If.else^.Kind = Tree.Stats0);
  4077.       yyMatch [6] := (yyt^.If.else^.Kind = Tree.Stats0);
  4078.       yyMatch [7] := (yyt^.If.then^.Kind = Tree.Stats0);
  4079.    --------------------------------------------- *)
  4080.       state := 1;
  4081.       state := yyComb [state + yyTraverse (yyt^.If.bExpr)];
  4082.       state := yyComb [state + yyTraverse (yyt^.If.then)];
  4083.       state := yyComb [state + yyTraverse (yyt^.If.else)];
  4084.       match := SYSTEM.ADR (yySets [state]);
  4085. .HS
  4086.       yyMatch [3] := (3 IN match^[0]) & (          (* line 86 Trans.estra *)
  4087.     BFold (yyt^.If.bExpr) = TRUE     );
  4088.       yyMatch [4] := (4 IN match^[0]) & (          (* line 95 Trans.estra *)
  4089.     BFold (yyt^.If.bExpr) = FALSE     );
  4090.       yyMatch [5] := (5 IN match^[0]);
  4091.       yyMatch [6] := (6 IN match^[0]);
  4092.       yyMatch [7] := (7 IN match^[0]);
  4093. (* --- bottom-up pattern-matching --- *)
  4094. .HS
  4095.       IF yyMatch [3] THEN
  4096.         cost := 0
  4097.         + CostBFold (yyt^.If.bExpr)
  4098.         + CostCode (yyt^.If.then);
  4099.         IF cost < info^.Code.Cost THEN
  4100.           info^.Code.Cost := cost;
  4101.           info^.Code.Proc := yyF3Code;
  4102.         END;
  4103.       END;
  4104. .HS
  4105.       IF yyMatch [4] THEN
  4106.         cost := 0
  4107.         + CostBFold (yyt^.If.bExpr)
  4108.         + CostCode (yyt^.If.else);
  4109.         IF cost < info^.Code.Cost THEN
  4110.           info^.Code.Cost := cost;
  4111.           info^.Code.Proc := yyF4Code;
  4112.         END;
  4113.       END;
  4114. .HS
  4115.       IF yyMatch [5] THEN
  4116.         cost := 0;
  4117.         IF cost < info^.Code.Cost THEN
  4118.           info^.Code.Cost := cost;
  4119.           info^.Code.Proc := yyF5Code;
  4120.         END;
  4121.       END;
  4122. .HS
  4123.       IF yyMatch [6] THEN
  4124.         cost := 3
  4125.         + CostCode (yyt^.If.bExpr)
  4126.         + CostCode (yyt^.If.then);
  4127.         IF cost < info^.Code.Cost THEN
  4128.           info^.Code.Cost := cost;
  4129.           info^.Code.Proc := yyF6Code;
  4130.         END;
  4131.       END;
  4132. .HS
  4133.       IF yyMatch [7] THEN
  4134.         cost := 4
  4135.         + CostCode (yyt^.If.bExpr)
  4136.         + CostCode (yyt^.If.else);
  4137.         IF cost < info^.Code.Cost THEN
  4138.           info^.Code.Cost := cost;
  4139.           info^.Code.Proc := yyF7Code;
  4140.         END;
  4141.       END;
  4142. .HS
  4143.       cost := 4
  4144.       + CostCode (yyt^.If.bExpr)
  4145.       + CostCode (yyt^.If.then)
  4146.       + CostCode (yyt^.If.else);
  4147.       IF cost < info^.Code.Cost THEN
  4148.         info^.Code.Cost := cost;
  4149.         info^.Code.Proc := yyF8Code;
  4150.       END;
  4151. .HS
  4152.   | Tree.Assign:
  4153. (* ------ simple pattern-matching ------
  4154.       yyTraverse (yyt^.Assign.index);
  4155.       yyTraverse (yyt^.Assign.aExpr);
  4156.       INCL (info^.yyClasses [yyCstat DIV yyBitsPerBitset], yyCstat MOD yyBitsPerBitset); 
  4157.    --------------------------------------------- *)
  4158.       state := 19;
  4159.       state := yyComb [state + yyTraverse (yyt^.Assign.index)];
  4160.       state := yyComb [state + yyTraverse (yyt^.Assign.aExpr)];
  4161. (* --- bottom-up pattern-matching --- *)
  4162. .HS
  4163. .HS
  4164.       cost := 1
  4165.       + CostCode (yyt^.Assign.index)
  4166.       + CostCode (yyt^.Assign.aExpr);
  4167.       IF cost < info^.Code.Cost THEN
  4168.         info^.Code.Cost := cost;
  4169.         info^.Code.Proc := yyF9Code;
  4170.       END;
  4171. .HS
  4172.   | Tree.Plus:
  4173. (* ------ simple pattern-matching ------
  4174.       yyTraverse (yyt^.Plus.lo);
  4175.       yyTraverse (yyt^.Plus.ro);
  4176.       INCL (info^.yyClasses [yyCaExpr DIV yyBitsPerBitset], yyCaExpr MOD yyBitsPerBitset); 
  4177.       IF yyClass (yyt^.Plus.lo, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset) 
  4178.        & yyClass (yyt^.Plus.ro, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset) THEN
  4179.         INCL (info^.yyClasses [yyCaConst DIV yyBitsPerBitset], yyCaConst MOD yyBitsPerBitset);
  4180.       END;
  4181. .HS
  4182.       yyMatch [12] := yyClass (yyt^.Plus.lo, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset)
  4183.        & yyClass (yyt^.Plus.ro, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset);
  4184.       yyMatch [19] := yyClass (yyt^.Plus.lo, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset)
  4185.        & yyClass (yyt^.Plus.ro, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset);
  4186.    --------------------------------------------- *)
  4187.       state := 50;
  4188.       state := yyComb [state + yyTraverse (yyt^.Plus.lo)];
  4189.       state := yyComb [state + yyTraverse (yyt^.Plus.ro)];
  4190.       match := SYSTEM.ADR (yySets [state]);
  4191. .HS
  4192.       yyMatch [12] := (12 IN match^[0]);
  4193.       yyMatch [19] := (19 IN match^[0]);
  4194. (* --- bottom-up pattern-matching --- *)
  4195. .HS
  4196.       cost := 1
  4197.       + CostCode (yyt^.Plus.lo)
  4198.       + CostCode (yyt^.Plus.ro);
  4199.       IF cost < info^.Code.Cost THEN
  4200.         info^.Code.Cost := cost;
  4201.         info^.Code.Proc := yyF10Code;
  4202.       END;
  4203. .HS
  4204.       IF yyMatch [12] THEN
  4205.         cost := 1
  4206.         + CostCode (yyt^.Plus.lo)
  4207.         + CostCode (yyt^.Plus.ro);
  4208.         IF cost < info^.Code.Cost THEN
  4209.           info^.Code.Cost := cost;
  4210.           info^.Code.Proc := yyF12Code;
  4211.         END;
  4212.       END;
  4213. .HS
  4214.       IF yyMatch [19] THEN
  4215.         cost := 1
  4216.         + CostAFold (yyt^.Plus.lo)
  4217.         + CostAFold (yyt^.Plus.ro);
  4218.         IF cost < info^.AFold.Cost THEN
  4219.           info^.AFold.Cost := cost;
  4220.           info^.AFold.Proc := yyF19AFold;
  4221.         END;
  4222.       END;
  4223. .HS
  4224.   | Tree.aIdent:
  4225. (* ------ simple pattern-matching ------
  4226.       INCL (info^.yyClasses [yyCindex DIV yyBitsPerBitset], yyCindex MOD yyBitsPerBitset); 
  4227.       INCL (info^.yyClasses [yyCaExpr DIV yyBitsPerBitset], yyCaExpr MOD yyBitsPerBitset); 
  4228.    --------------------------------------------- *)
  4229.       state := 17;
  4230. (* --- bottom-up pattern-matching --- *)
  4231. .HS
  4232. .HS
  4233.       cost := 1;
  4234.       IF cost < info^.Code.Cost THEN
  4235.         info^.Code.Cost := cost;
  4236.         info^.Code.Proc := yyF13Code;
  4237.       END;
  4238. .HS
  4239.   | Tree.Const:
  4240. (* ------ simple pattern-matching ------
  4241.       INCL (info^.yyClasses [yyCaConst DIV yyBitsPerBitset], yyCaConst MOD yyBitsPerBitset); 
  4242.       INCL (info^.yyClasses [yyCaExpr DIV yyBitsPerBitset], yyCaExpr MOD yyBitsPerBitset); 
  4243.    --------------------------------------------- *)
  4244.       state := 16;
  4245. (* --- bottom-up pattern-matching --- *)
  4246. .HS
  4247. .HS
  4248.       cost := 1;
  4249.       IF cost < info^.Code.Cost THEN
  4250.         info^.Code.Cost := cost;
  4251.         info^.Code.Proc := yyF11Code;
  4252.       END;
  4253. .HS
  4254.       cost := 1;
  4255.       IF cost < info^.AFold.Cost THEN
  4256.         info^.AFold.Cost := cost;
  4257.         info^.AFold.Proc := yyF18AFold;
  4258.       END;
  4259. .HS
  4260.   | Tree.Less:
  4261. (* ------ simple pattern-matching ------
  4262.       yyTraverse (yyt^.Less.lo);
  4263.       yyTraverse (yyt^.Less.ro);
  4264.       INCL (info^.yyClasses [yyCbExpr DIV yyBitsPerBitset], yyCbExpr MOD yyBitsPerBitset); 
  4265.       IF yyClass (yyt^.Less.lo, yyCbConst MOD yyBitsPerBitset, yyCbConst DIV yyBitsPerBitset) 
  4266.        & yyClass (yyt^.Less.ro, yyCbConst MOD yyBitsPerBitset, yyCbConst DIV yyBitsPerBitset) THEN
  4267.         INCL (info^.yyClasses [yyCbConst DIV yyBitsPerBitset], yyCbConst MOD yyBitsPerBitset);
  4268.       END;
  4269. .HS
  4270.       yyMatch [22] := yyClass (yyt^.Less.lo, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset)
  4271.        & yyClass (yyt^.Less.ro, yyCaConst MOD yyBitsPerBitset, yyCaConst DIV yyBitsPerBitset);
  4272.    --------------------------------------------- *)
  4273.       state := 73;
  4274.       state := yyComb [state + yyTraverse (yyt^.Less.lo)];
  4275.       state := yyComb [state + yyTraverse (yyt^.Less.ro)];
  4276.       match := SYSTEM.ADR (yySets [state]);
  4277. .HS
  4278.       yyMatch [22] := (22 IN match^[0]);
  4279. (* --- bottom-up pattern-matching --- *)
  4280. .HS
  4281.       cost := 1
  4282.       + CostCode (yyt^.Less.lo)
  4283.       + CostCode (yyt^.Less.ro);
  4284.       IF cost < info^.Code.Cost THEN
  4285.         info^.Code.Cost := cost;
  4286.         info^.Code.Proc := yyF16Code;
  4287.       END;
  4288. .HS
  4289.       IF yyMatch [22] THEN
  4290.         cost := 0
  4291.         + CostAFold (yyt^.Less.lo)
  4292.         + CostAFold (yyt^.Less.ro);
  4293.         IF cost < info^.BFold.Cost THEN
  4294.           info^.BFold.Cost := cost;
  4295.           info^.BFold.Proc := yyF22BFold;
  4296.         END;
  4297.       END;
  4298. .HS
  4299.   | Tree.bIdent:
  4300. (* ------ simple pattern-matching ------
  4301.       INCL (info^.yyClasses [yyCbExpr DIV yyBitsPerBitset], yyCbExpr MOD yyBitsPerBitset); 
  4302.    --------------------------------------------- *)
  4303.       state := 23;
  4304. (* --- bottom-up pattern-matching --- *)
  4305. .HS
  4306. .HS
  4307.       cost := 1;
  4308.       IF cost < info^.Code.Cost THEN
  4309.         info^.Code.Cost := cost;
  4310.         info^.Code.Proc := yyF17Code;
  4311.       END;
  4312. .HS
  4313.   | Tree.True:
  4314. (* ------ simple pattern-matching ------
  4315.       INCL (info^.yyClasses [yyCbConst DIV yyBitsPerBitset], yyCbConst MOD yyBitsPerBitset); 
  4316.       INCL (info^.yyClasses [yyCbExpr DIV yyBitsPerBitset], yyCbExpr MOD yyBitsPerBitset); 
  4317.    --------------------------------------------- *)
  4318.       state := 18;
  4319. (* --- bottom-up pattern-matching --- *)
  4320. .HS
  4321. .HS
  4322.       cost := 1;
  4323.       IF cost < info^.Code.Cost THEN
  4324.         info^.Code.Cost := cost;
  4325.         info^.Code.Proc := yyF14Code;
  4326.       END;
  4327. .HS
  4328.       cost := 0;
  4329.       IF cost < info^.BFold.Cost THEN
  4330.         info^.BFold.Cost := cost;
  4331.         info^.BFold.Proc := yyF20BFold;
  4332.       END;
  4333. .HS
  4334.   | Tree.False:
  4335. (* ------ simple pattern-matching ------
  4336.       INCL (info^.yyClasses [yyCbConst DIV yyBitsPerBitset], yyCbConst MOD yyBitsPerBitset); 
  4337.       INCL (info^.yyClasses [yyCbExpr DIV yyBitsPerBitset], yyCbExpr MOD yyBitsPerBitset); 
  4338.    --------------------------------------------- *)
  4339.       state := 19;
  4340. (* --- bottom-up pattern-matching --- *)
  4341. .HS
  4342. .HS
  4343.       cost := 1;
  4344.       IF cost < info^.Code.Cost THEN
  4345.         info^.Code.Cost := cost;
  4346.         info^.Code.Proc := yyF15Code;
  4347.       END;
  4348. .HS
  4349.       cost := 0;
  4350.       IF cost < info^.BFold.Cost THEN
  4351.         info^.BFold.Cost := cost;
  4352.         info^.BFold.Proc := yyF21BFold;
  4353.       END;
  4354. .HS
  4355.   END;
  4356. (* ------ simple pattern-matching ------
  4357.    --------------------------------------------- *)
  4358.   RETURN state;
  4359. (* --- bottom-up pattern-matching --- *)
  4360. END yyTraverse;
  4361. .HS
  4362. (* ------ simple pattern-matching ------
  4363. PROCEDURE BeginTrans;
  4364. BEGIN
  4365.    --------------------------------------------- *)
  4366. PROCEDURE yyErrorCheck (i: INTEGER; s1, s2: ARRAY OF CHAR);
  4367. BEGIN
  4368.   IF i < 0 THEN
  4369.     IO.WriteS (IO.StdError, s1);
  4370.     IO.WriteS (IO.StdError, s2);
  4371.     IO.WriteNl (IO.StdError); IO.CloseIO; HALT;
  4372.   END;
  4373. END yyErrorCheck;
  4374. .HS
  4375. PROCEDURE BeginTrans;
  4376. VAR yyf: SystemIO.tFile; yyi: INTEGER;
  4377. BEGIN
  4378.   yyf := SystemIO.OpenInput (TransTabName);
  4379.   yyErrorCheck (yyf, 'cannot open ', TransTabName);
  4380.   yyi := SystemIO.Read (yyf, SYSTEM.ADR (yySets), SYSTEM.TSIZE (yySetsType));
  4381.   yyErrorCheck (yyi, 'cannot read ', TransTabName);
  4382.   yyi := SystemIO.Read (yyf, SYSTEM.ADR (yyComb), SYSTEM.TSIZE (yyCombType));
  4383.   yyErrorCheck (yyi, 'cannot read ', TransTabName);
  4384.   SystemIO.Close (yyf);
  4385. (* --- bottom-up pattern-matching --- *)
  4386.     (* line 12 Trans.estra *)
  4387. .HS
  4388. BeginIO;
  4389. .HS
  4390. END BeginTrans;
  4391. .HS
  4392. PROCEDURE DoTrans (yyt: Tree.tTree);
  4393. VAR state: yyStateType;
  4394. BEGIN
  4395. (* ------ simple pattern-matching ------
  4396.   yyTraverse (yyt);
  4397.    --------------------------------------------- *)
  4398.   state := yyTraverse (yyt);
  4399. (* --- bottom-up pattern-matching --- *)
  4400.   Code (yyt);
  4401.   yyReleaseHeap;
  4402. END DoTrans;
  4403. .HS
  4404. PROCEDURE CloseTrans;
  4405. BEGIN
  4406.     (* line 16 Trans.estra *)
  4407. .HS
  4408. CloseIO;
  4409. .HS
  4410. END CloseTrans;
  4411. .HS
  4412. BEGIN
  4413.   TransTabName := 'Trans.tab';
  4414.   WITH yyInfo DO
  4415. (* ------ simple pattern-matching ------
  4416.     yyClasses [0] := {};
  4417.    --------------------------------------------- *)
  4418. (* --- bottom-up pattern-matching --- *)
  4419.     Code.Cost := yyInfinite;
  4420.     Code.Proc := yyECode;
  4421.     AFold.Cost := yyInfinite;
  4422.     AFold.Proc := yyEAFold;
  4423.     BFold.Cost := yyInfinite;
  4424.     BFold.Proc := yyEBFold;
  4425.   END;
  4426.   yyBlockList:= NIL;
  4427.   yyPoolFreePtr:= NIL;
  4428.   yyPoolEndPtr:= NIL;
  4429. END Trans.
  4430. .)l
  4431. .oh ''%''
  4432. .bp
  4433. .UH 2 "Anhang B3: Bottom-Up Pattern-Matching Automat"
  4434. .lp
  4435. .b "Relevante Muster:"
  4436. .TS
  4437. rl.
  4438. .sz -2
  4439. p\*<0\*> =    Stats (:, :)
  4440. p\*<0\*> =    Stats (:, :)
  4441. p\*<1\*> =    Stats0 ()
  4442. p\*<2\*> =    If (bConst, :, :)
  4443. p\*<3\*> =    If (:, :, Stats0 ())
  4444. p\*<4\*> =    If (:, Stats0 (), :)
  4445. p\*<5\*> =    If (:, :, :)
  4446. p\*<6\*> =    ':=' (:, :)
  4447. p\*<7\*> =    '+' (:, :)
  4448. p\*<8\*> =    aConst
  4449. p\*<9\*> =    index
  4450. p\*<10\*> =    '<' (:, :)
  4451. p\*<11\*> =    bIdent ()
  4452. p\*<12\*> =    bConst
  4453. p\*<13\*> =    Const ()
  4454. p\*<14\*> =    '+' (aConst, aConst)
  4455. p\*<15\*> =    True ()
  4456. p\*<16\*> =    False ()
  4457. p\*<17\*> =    '<' (aConst, aConst)
  4458. p\*<18\*> =    :
  4459. .TE
  4460. .bp
  4461. .b "Zust\*ande:"
  4462. .TS
  4463. rl.
  4464. .sz -2
  4465. q\*<0\*> =    { p\*<0\*>, p\*<18\*> }
  4466. q\*<1\*> =    { p\*<1\*>, p\*<18\*> }
  4467. q\*<2\*> =    { p\*<2\*>, p\*<3\*>, p\*<4\*>, p\*<5\*>, p\*<18\*> }
  4468. q\*<3\*> =    { p\*<2\*>, p\*<3\*>, p\*<5\*>, p\*<18\*> }
  4469. q\*<4\*> =    { p\*<2\*>, p\*<4\*>, p\*<5\*>, p\*<18\*> }
  4470. q\*<5\*> =    { p\*<2\*>, p\*<5\*>, p\*<18\*> }
  4471. q\*<6\*> =    { p\*<3\*>, p\*<4\*>, p\*<5\*>, p\*<18\*> }
  4472. q\*<7\*> =    { p\*<3\*>, p\*<5\*>, p\*<18\*> }
  4473. q\*<8\*> =    { p\*<4\*>, p\*<5\*>, p\*<18\*> }
  4474. q\*<9\*> =    { p\*<5\*>, p\*<18\*> }
  4475. q\*<10\*> =    { p\*<6\*>, p\*<18\*> }
  4476. q\*<11\*> =    { p\*<7\*>, p\*<8\*>, p\*<14\*>, p\*<18\*> }
  4477. q\*<12\*> =    { p\*<7\*>, p\*<8\*>, p\*<18\*> }
  4478. q\*<13\*> =    { p\*<7\*>, p\*<18\*> }
  4479. q\*<14\*> =    { p\*<8\*>, p\*<13\*>, p\*<18\*> }
  4480. q\*<15\*> =    { p\*<8\*>, p\*<18\*> }
  4481. q\*<16\*> =    { p\*<9\*>, p\*<18\*> }
  4482. q\*<17\*> =    { p\*<10\*>, p\*<12\*>, p\*<17\*>, p\*<18\*> }
  4483. q\*<18\*> =    { p\*<10\*>, p\*<12\*>, p\*<18\*> }
  4484. q\*<19\*> =    { p\*<10\*>, p\*<18\*> }
  4485. q\*<20\*> =    { p\*<11\*>, p\*<18\*> }
  4486. q\*<21\*> =    { p\*<12\*>, p\*<15\*>, p\*<18\*> }
  4487. q\*<22\*> =    { p\*<12\*>, p\*<16\*>, p\*<18\*> }
  4488. q\*<23\*> =    { p\*<12\*>, p\*<18\*> }
  4489. q\*<24\*> =    { p\*<18\*> }
  4490. .TE
  4491. .bp
  4492. .b "Zustands\*ubergangsfunktionen:"
  4493. .TS
  4494. llllll.
  4495. .sz -2
  4496. Stats    [q\*<2\*> - q\*<10\*>, q\*<24\*>]    [q\*<0\*>, q\*<1\*>, q\*<24\*>]        \(eq    q\*<0\*>
  4497. .HS
  4498. Stats0                \(eq    q\*<1\*>
  4499. .HS
  4500. If    [q\*<17\*>, q\*<18\*>, q\*<21\*>, q\*<22\*>, q\*<23\*>]    [q\*<0\*>, q\*<24\*>]    [q\*<0\*>, q\*<24\*>]    \(eq    q\*<5\*>
  4501. If    [q\*<17\*>, q\*<18\*>, q\*<21\*>, q\*<22\*>, q\*<23\*>]    [q\*<0\*>, q\*<24\*>]    [q\*<1\*>]    \(eq    q\*<3\*>
  4502. If    [q\*<17\*>, q\*<18\*>, q\*<21\*>, q\*<22\*>, q\*<23\*>]    [q\*<1\*>]    [q\*<0\*>, q\*<24\*>]    \(eq    q\*<4\*>
  4503. If    [q\*<17\*>, q\*<18\*>, q\*<21\*>, q\*<22\*>, q\*<23\*>]    [q\*<1\*>]    [q\*<1\*>]    \(eq    q\*<2\*>
  4504. If    [q\*<19\*>, q\*<20\*>, q\*<24\*>]    [q\*<0\*>, q\*<24\*>]    [q\*<0\*>, q\*<24\*>]    \(eq    q\*<9\*>
  4505. If    [q\*<19\*>, q\*<20\*>, q\*<24\*>]    [q\*<0\*>, q\*<24\*>]    [q\*<1\*>]    \(eq    q\*<7\*>
  4506. If    [q\*<19\*>, q\*<20\*>, q\*<24\*>]    [q\*<1\*>]    [q\*<0\*>, q\*<24\*>]    \(eq    q\*<8\*>
  4507. If    [q\*<19\*>, q\*<20\*>, q\*<24\*>]    [q\*<1\*>]    [q\*<1\*>]    \(eq    q\*<6\*>
  4508. .HS
  4509. \&':='    [q\*<16\*>, q\*<24\*>]    [q\*<11\*> - q\*<16\*>, q\*<24\*>]        \(eq    q\*<10\*>
  4510. .HS
  4511. \&'+'    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]        \(eq    q\*<11\*>
  4512. \&'+'    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]    [q\*<13\*>, q\*<16\*>, q\*<24\*>]        \(eq    q\*<13\*>
  4513. \&'+'    [q\*<13\*>, q\*<16\*>, q\*<24\*>]    [q\*<11\*> - q\*<16\*>, q\*<24\*>]        \(eq    q\*<13\*>
  4514. .HS
  4515. aIdent                \(eq    q\*<16\*>
  4516. .HS
  4517. Const                \(eq    q\*<14\*>
  4518. .HS
  4519. \&'<'    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]        \(eq    q\*<17\*>
  4520. \&'<'    [q\*<11\*>, q\*<12\*>, q\*<14\*>, q\*<15\*>]    [q\*<13\*>, q\*<16\*>, q\*<24\*>]        \(eq    q\*<19\*>
  4521. \&'<'    [q\*<13\*>, q\*<16\*>, q\*<24\*>]    [q\*<11\*> - q\*<16\*>, q\*<24\*>]        \(eq    q\*<19\*>
  4522. .HS
  4523. bIdent                \(eq    q\*<20\*>
  4524. .HS
  4525. True                \(eq    q\*<21\*>
  4526. .HS
  4527. False                \(eq    q\*<22\*>
  4528. .TE
  4529. .BP
  4530. .lp
  4531. .fi
  4532. .sp
  4533. .b
  4534. .sz 12
  4535. .(x
  4536.  
  4537. \fBLiteraturhinweise\fP
  4538. .)x
  4539. .de []
  4540. .b
  4541. Literaturhinweise
  4542. .lp
  4543. ..
  4544. .[]
  4545. .[-
  4546. .ds [F AGT87
  4547. .ds [A Alfred V. Aho
  4548. .as [A \*(c]Mahadevan Ganapathi
  4549. .as [A \*(m]Steven W. K. Tjiang
  4550. .ds [T Code Generation Using Tree Matching and Dynamic Programming
  4551. .ds [I AT&T Bell Laboratories
  4552. .ds [D 1987
  4553. .][
  4554. .[-
  4555. .ds [F BMW87
  4556. .ds [A J\*urgen B\*orstler
  4557. .as [A \*(c]Ulrich M\*oncke
  4558. .as [A \*(m]Reinhard Wilhelm
  4559. .ds [T Table Compression for Tree Automata
  4560. .ds [D 1987
  4561. .ds [V 12
  4562. .ds [J Aachener Informatik-Berichte
  4563. .][
  4564. .[-
  4565. .ds [F Emm88
  4566. .ds [A Helmut Emmelmann
  4567. .ds [T Automatische Erzeugung effizienter Codegeneratoren
  4568. .ds [I Diplomarbeit, GMD Forschungsstelle an der Universit\*at Karlsruhe
  4569. .ds [D Sep. 1988
  4570. .][
  4571. .[-
  4572. .ds [F Gro89
  4573. .ds [A Josef Grosch
  4574. .ds [T Ast - A generator for Abstract Syntax Trees
  4575. .ds [I GMD Forschungsstelle an der Universit\*at Karlsruhe
  4576. .ds [V 14
  4577. .ds [D Feb. 1989
  4578. .][
  4579. .[-
  4580. .ds [F HoO82
  4581. .ds [A Christoph M. Hoffmann
  4582. .as [A \*(n]Michael J. O'Donnell
  4583. .ds [T Pattern Matching in Trees
  4584. .ds [J J. ACM
  4585. .ds [V 29
  4586. .ds [N 1
  4587. .nr [P 1
  4588. .ds [P 68-95
  4589. .ds [D Jan. 1982
  4590. .][
  4591. .[-
  4592. .ds [F KeR83
  4593. .ds [A Brian W. Kernighan
  4594. .as [A \*(n]Dennis M. Ritchie
  4595. .ds [T Programmieren in C
  4596. .ds [I Hanser M\*unchen
  4597. .ds [D 1983
  4598. .][
  4599. .[-
  4600. .ds [F Knu68
  4601. .ds [A D. E. Knuth
  4602. .ds [T Semantics of Context-Free Languages
  4603. .nr [P 1
  4604. .ds [P 127-146
  4605. .ds [J Mathematical Systems Theory
  4606. .ds [V 2
  4607. .ds [D June 1968
  4608. .ds [N 2
  4609. .][
  4610. .[-
  4611. .ds [F MWW84
  4612. .ds [A Ulrich M\*onke
  4613. .as [A \*(c]Beatrix Weisgerber
  4614. .as [A \*(m]Reinhard Wilhelm
  4615. .ds [T How to Implement a System for Manipulation of Attributed Trees
  4616. .ds [B Informatik Fachberichte
  4617. .ds [V 77
  4618. .ds [E U. Ammann
  4619. .nr [E 1
  4620. .ds [S Programmiersprachen und Programmentwicklung
  4621. .ds [I Springer Verlag
  4622. .ds [D Mar. 1984
  4623. .][
  4624. .[-
  4625. .ds [F Wir85
  4626. .ds [A Niklaus Wirth
  4627. .ds [T Programmieren in Modula-2
  4628. .ds [I Springer Verlag
  4629. .ds [D 1985
  4630. .][
  4631. .he '\s-2\fRInhaltsverzeichnis\fP\s+2''%'
  4632. .bp 2
  4633. .lp
  4634. .xp
  4635.